裸Trie，不想多说
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<cstdlib> 7 using namespace std; 8 char s[100005]; 9 int ch[100005][15],tot=1; 10 bool bo[100005]; 11 void init() 12 { 13 memset(ch,0,sizeof(ch)); 14 memset(bo,false,sizeof(bo)); tot=1; 15 } 16 bool insert(char *st) 17 { 18 int u=1,n=strlen(st); bool flag=false; 19 for (int i=0; i<n; i++){ 20 int c=st[i]-'0'; 21 if (!ch[u][c]) ch[u][c]=++tot; 22 else if (i==n-1) flag=true; 23 if (bo[u]) flag=true; 24 u=ch[u][c]; 25 } 26 bo[u]=true; return flag; 27 } 28 int main() 29 { 30 int js=1; bool flag=false; 31 while (cin>>s){ 32 if (s[0]=='9' && (s[1]<'0' || s[1]>'9')) { 33 if (flag) printf("Set %d is not immediately decodable ",js); else printf("Set %d is immediately decodable ",js); 34 js++; flag=false; init(); continue; 35 } 36 flag=flag|insert(s); 37 } 38 return 0; 39 }
miao~~