HDU1247 Hat’s Words（Trie树）

常规做法是枚举每个字符串每个位置，时间复杂度O(n*len*len)，（建字典树O(n*len)）。

然而我看这题第一眼想的是时间复杂度O(n*len)的算法。。就是建正反两棵字典树，每个字符串跑分别跑正反一遍字典树，再看看正反跑的结果能不能拼成原串。

然而常数太大了点，并没什么卵用。。

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define MAXL 22

 #define MAXN 50100

 int ch0[MAXN*MAXL][],tn0,ch1[MAXN*MAXL][],tn1;

 bool flag[][MAXN*MAXL];

 void insert(char *s){

     int x=,len=strlen(s);

     for(int i=; i<len; ++i){

         int y=s[i]-'a';

         if(ch0[x][y]==) ch0[x][y]=++tn0;

         x=ch0[x][y];

     }

     flag[][x]=;

     x=;

     for(int i=len-; i>=; --i){

         int y=s[i]-'a';

         if(ch1[x][y]==) ch1[x][y]=++tn1;

         x=ch1[x][y];

     }

     flag[][x]=;

 }

 char path[MAXL];

 bool vis[][MAXL];

 void query(int len){

     memset(vis,,sizeof(vis));

     int x=;

     for(int i=; i<len; ++i){

         int y=path[i]-'a';

         if(ch0[x][y]==) break;

         x=ch0[x][y];

         if(flag[][x]) vis[][i]=;

     }

     x=;

     for(int i=len-; i>=; --i){

         int y=path[i]-'a';

         if(ch1[x][y]==) break;

         x=ch1[x][y];

         if(flag[][x]) vis[][i]=;

     }

 }

 void dfs(int x,int k){

     if(flag[][x]){

         query(k);

         bool ishat=;

         for(int i=; i<k; ++i){

             if(vis[][i-] && vis[][i]){

                 ishat=;

                 break;

             }

         }

         if(ishat){

             for(int i=; i<k; ++i) putchar(path[i]);

             putchar('\n');

         }

     }

     for(int i=; i<; ++i){

         if(ch0[x][i]){

             path[k]=i+'a';

             dfs(ch0[x][i],k+);

         }

     }

 }

 int main(){

     char str[MAXL];

     while(~scanf("%s",str)) insert(str);

     dfs(,);

     return ;

 }

巴特西

HDU1247 Hat’s Words（Trie树）

最新文章

热门文章