UVA10391 UVA10391 复合词 Compound Words 题解

· · 题解

提示：萌新不会写substr，所以本篇是适合新手阅读的题解。

PART 01 读入

我们可以利用C++语言的特性，把字符串读入写入循环条件里：

for( ; cin>>s[cnt] ; ){ //C++语言特性
    cnt++;
}

为了避免变量重名，也为了为字符串数组提供指针，用 cnt 表示目前读入的下标，而最终的 cnt 就是字符串的数量。

PART 02 算法

2.1：字符串匹配

我们知道判断一个字符串是否是复合串的方法就是将其分成两半，然后再分别判断分出来的两个字符串是否存在。因此我们可以使用 map 来存储字符串是否存在过。

map <string,bool> p;
for( ; cin>>s[cnt] ; ){
    p[s[cnt]] = true; //如果该字符串存在了，map 值变为 true
    cnt++;
}

2.2：隔板法

如果我们想要把一个字符串分成两个部分，可以理解为将一个整体用一块隔板将其分开。所以不妨用一个循环变量当做隔板进行字符串分割。

for(int j = 1 ; j < s[i].length() ; j++){ // j 作为隔板分割字符串
        for(int k = 0 ; k < j ; k++){
            a += s[i][k]; // j 前面的字符都变成前半部分的串（a）
        }
        for(int k = j ; k < s[i].length() ; k++){
            b += s[i][k]; // j 后面的字符都变成后半部分的串（b）
        }
}

注意，有些同学认为当存在两个相同的串时，也认为其中一个是复合串，但其实这样的串也属于普通串的范畴。因此，我们可以发现 b 串至少可以取到最后一个字符，排除了有相同串的情况。

2.3：判断情况

这里便可以体现出 map 的作用。

只要得到了 a 串与 b 串我们就可以往循环里面加入判断，即通过 map 的布尔值来判断是否存在过。

for(int j = 1 ; j < s[i].length() ; j++){
        for(int k = 0 ; k < j ; k++){
            a += s[i][k];
        }
        for(int k = j ; k < s[i].length() ; k++){
            b += s[i][k];
        }
        if(p[a] && p[b]){
            cout<< s[i] <<endl;
            break; //就是这里，如果不加就会WA掉，因为可能一个串有多种分割办法。
        }
}

值得一提的是，为了防止拼法有多种导致多种输出，有必要在判断完后进行 break 。

最后要记住，清空 A 串与 B 串以供下次使用。

AC代码

AC记录

#include <bits/stdc++.h>
using namespace std;
map <string,bool> p;
string s[120030],a,b;
int cnt;
int main(){
    for( ; cin>>s[cnt] ; ){
        p[s[cnt]] = true;
        cnt++;
    }
    for(int i = 0 ; i < cnt ; i++){
        for(int j = 1 ; j < s[i].length() ; j++){
            a = "";
            b = "";
            for(int k = 0 ; k < j ; k++){
                a+=s[i][k];
            }
            for(int k = j ; k < s[i].length() ; k++){
                b+=s[i][k];
            }
            if(p[a] && p[b]){
                cout<< s[i] <<endl;
                break;
            }
        }
    }
    return 0;
}