trie

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 const int MAX=1001; 8 char s[MAX]; 9 int sz,len;10 int trie[MAX*MAX][26];11 int minp[MAX*MAX],maxp[MAX*MAX],dep[MAX*MAX];12 void insert_trie(char *str,int d)13 {14  int rt=0;15  for (int i=0;str[i];i++)16  {17   int t=str[i]-'a';18   if (!trie[rt][t]){19    trie[rt][t]=++sz;20    memset(trie[sz],0,sizeof(trie[sz]));21    minp[sz]=MAX;maxp[sz]=0;22    dep[sz]=i+1;23   }24   rt=trie[rt][t];25   if (i+d>maxp[rt]) maxp[rt]=i+d;26   if (i+d
           
            len) return;28 29 }30 }31 int cnt;32 void find_trie(int rt)33 {34 35 for (int i=0;i<26;i++){36 if (trie[rt][i]){37 int t=trie[rt][i];38 if (minp[t]+dep[t]<=maxp[t]) {39 cnt++;40 find_trie(t);41 }42 43 44 }45 }46 }47 int main()48 {49 freopen("C:\in.txt","r",stdin);50 while (gets(s))51 {52 if (s[0]=='#') break;53 char *str=s;54 len=strlen(s);55 memset(trie[0],0,sizeof(trie[0]));56 sz=0;57 for (int i=0;s[i];i++)58 {59 insert_trie(str,i);60 str++;61 }62 cnt=0;63 find_trie(0);64 printf("%d\n",cnt);65 } 66 67 return 0;68 }