HDU 3518

http://acm.hdu.edu.cn/showproblem.php?pid=3518
trie
View Code
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<iostream>
 5 #include<algorithm>
 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<minp[rt]) minp[rt]=i+d;
27   if (minp[rt]+dep[rt]>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 }