HDU-1247-Hat’s Words(字典树)

Hat’s Words

输出字符串集合中哪些可以由字符串集合中的其他两个字符串组成

#include<bits/stdc++.h>
using namespace std;
const int M=50050;
int tree[M][26];
int vis[M];
int pos=1;
string s;
map<int,string>mp;
void insert(string s)
{
    int len=s.size( );
    int root=0;
    for(int i=0;i<len;i++)
    {
        int x=s[i]-'a';
        if(!tree[root][x])
        {
            tree[root][x]=pos++;
        }
        root=tree[root][x];
    }
    vis[root]=1;
}
bool findprefix(string s)
{
    int len=s.size( );
    int root=0;
    for(int i=0;i<len;i++)
    {
        int x=s[i]-'a';
        if(!tree[root][x])
        {
            return 0;
        }
        root=tree[root][x];
    }
    return vis[root];
}
int main( )
{
    int cnt=0;
    while(cin>>s)
    {
        mp[++cnt]=s;
        insert(s);
    }
    string str1,str2;
    for(int i=1;i<=cnt;i++)
    {
        s=mp[i];
        int len=s.size( );
        for(int j=1;j<len;j++)
        {
            str1=s.substr(0,j);
            str2=s.substr(j);
            if(findprefix(str1)&&findprefix(str2))
            {
                cout<<s<<endl;
                break;
            }
        }
    }
    return 0;
}