紫书第五章习题 5-5 Ducci 序列（Uva 10391)

题目链接：https://vjudge.net/problem/UVA-10391

Sample Input

a
alien
born
less
lien
never
nevertheless
new
newborn
the
zebra

Sample Output

alien
newborn

题意分析：给出字典中一堆单词，单词的输入方式是以字典序输入的。问：在这一堆单词中，有那些单词是通过其它两个单词组合而来的。按字典序升序输出这些单词(输入的时候就是字典序)。
思路：一开始想用字符匹配的方法，或者是find() or KMP，但是没法保证是由两个单词组成，比如abcd，abc，cd，这个abcd就可以通过，但不符合题目要求。因此方向就错了。后来参考资料。
第一个重点：应该需要用到map映射，map<string,bool>，类似桶的作用，把出现过的字符串全部都记录一下，并把对应的bool变为1。后面找的时候只要map[string]==0，就证明没有这个出现过这个单词。
第二个重点：是对字符串的分割，需要用到substr(int ,int)函数,str.substr(a,b)表示的是将字符串str从第a位开始一直向后取到b位，str.substr(a)表示的是从第a+1位取到最后一位。

#include<bits/stdc++.h>
using namespace std;
string s[120001];
map<string,int> voca;//用来判断是否存在子单词
int main()
{
    int n=0;
    while(cin>>s[n])
    {
        voca[s[n]]=1;//标记存在的子单词
        n++;
    }
    for(int i=0;i<n;i++)
    {
        string l,r;//将字符串拆分，左边和右边两个单词
        for(int j=0;j<s[i].length();j++)
        {
            l=s[i].substr(0,j);//从s[i][0]开始，往后取j位
            r=s[i].substr(j);//从s[i][j]开始，一直到末尾
            if(voca[l]!=0&&voca[r]!=0)//判断左右单词是否存在
            {
                cout<<s[i]<<endl;
                break;
            }
        }
    }
    return 0;
}

这本书上的内容非常的多，专题习题也非常丰富，难度适中（还没做到难的）。这样一章让我非常好地熟悉了许多stl的内容，并渐渐掌握，暂时还未涉及高深算法，但stl的基础打牢固，能为后来的学习省不少力气。