hdu 1247 字典树

拼搏现实的明天。 2022-08-05 11:19 67阅读 0赞

**给定一系列的单词，少于50000个，输出这些单词中由两个出现过的单词组成的单词。**

**开始用gets输入，无限wrong！猜测可能数据中有空行。**

**换了scanf就AC了。**

#include<bitset> //G++ 15ms
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=1000510;
    
    struct Trie
    {
        int next[27];
        bool flag;
        void init()
        {
            flag=0;
            mem(next,-1);
        }
    }trie[N];
    
    int total;
    
    void insert(char *a)
    {
        int n=strlen(a);
        int now=0,tmp,next;
        for(int i=0;i<n;i++)
        {
            tmp=a[i]-'a';
            next=trie[now].next[tmp];
            if(next==-1)
            {
                next=++total;
    
                trie[next].init();
                trie[now].next[tmp]=next;
            }
            now=next;
        }
        trie[now].flag=1;
    
    }
    
    bool ok(char * s,int i,int n)
    {
    
        int now=0,tmp,next;
        for(;i<n;i++)
        {
            tmp=s[i]-'a';
            next=trie[now].next[tmp];
            if(next==-1) return 0;
            now=next;
        }
    
        return trie[now].flag;
    
    }
    
    bool Find(char *s)
    {
        int now=0,tmp,next;
        int n=strlen(s);
        string t;
        for(int i=0;i<n;i++)
        {
            tmp=s[i]-'a';
    
            if(trie[now].flag)
            {
                if(ok(s,i,n)) return 1;
            }
            next=trie[now].next[tmp];
            now=next;
        }
    
        return 0;
    }
    
    char word[50005][51];
    
    int main()
    {
        total=0;
        trie[0].init();
        int i=0;
        while(~scanf("%s",word[i]))
        {
            //if(word[i][0]=='#')break;
            insert(word[i]);
            i++;
    
        }
        for(int j=0;j<i;j++)
        {
            if(Find(word[j]))
            {
                puts(word[j]);
            }
        }
        return 0;
    }