//暴力，從每一行的開始處開始尋找要查詢的字符 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;char str[100005];int main(){while(gets(str)){for(int i=0; str[i]; ++i)if(str[i]=='A'){if(strstr(str+i, "Apple") == str+i)printf("MAI MAI MAI!\n");}else if(str[i]=='i'){if(strstr(str+i, "iPhone") == str+i || strstr(str+i, "iPod") == str+i || strstr(str+i, "iPad") == str+i)printf("MAI MAI MAI!\n");}else if(str[i]=='S')if(strstr(str+i, "Sony") == str+i)printf("SONY DAFA IS GOOD!\n");}return 0; }
1 //將要匹配的字符串（也就是題目中查詢文本中出現的5個單詞）建立trie樹，然后生成AC_自動機..... 2 #include<iostream> 3 #include<cstring> 4 #include<queue> 5 #include<cstdio> 6 #include<algorithm> 7 using namespace std; 8 9 int trie[30][200]; 10 int vis[30], fail[6000];//vis標記的是單詞的末尾字符所在的節點 11 char str[][10] = {"Apple", "iPhone", "iPod", "iPad", "Sony"}; 12 int cnt; 13 void buildT(){ 14 for(int i=0; i<5; ++i){ 15 int u=0; 16 for(int j=0; str[i][j]; ++j){ 17 if(trie[u][str[i][j]] == 0) 18 trie[u][str[i][j]] = ++cnt; 19 u=trie[u][str[i][j]]; 20 } 21 vis[u]=1; 22 } 23 } 24 25 void getFail(){ 26 queue<int>q; 27 for(int i=0; i<200; ++i) 28 if(trie[0][i]) q.push(trie[0][i]); 29 while(!q.empty()){ 30 int u = q.front(); 31 q.pop(); 32 int v; 33 for(int i=0; i<200; ++i) 34 if(v = trie[u][i]){ 35 fail[v] = trie[fail[u]][i]; 36 q.push(v); 37 } 38 else 39 trie[u][i] = trie[fail[u]][i]; 40 } 41 } 42 43 void getText(char *ch){ 44 int u=0; 45 for(int i=0; ch[i]; ++i){ 46 int v = trie[u][ch[i]]; 47 u=v; 48 while(v){ 49 if(vis[v] && (ch[i]=='d' || ch[i]=='e')) 50 printf("MAI MAI MAI!\n"); 51 else if(vis[v] && ch[i]=='y') 52 printf("SONY DAFA IS GOOD!\n"); 53 v = fail[v]; 54 } 55 } 56 } 57 58 char text[10000]; 59 60 int main(){ 61 buildT(); 62 getFail(); 63 while(gets(text)){ 64 getText(text); 65 } 66 return 0; 67 }
?
)
_oracle)
