首页 > 代码库 > 2014 网选 5007 Post Robot(暴力或者AC_自动机(有点小题大作了))
2014 网选 5007 Post Robot(暴力或者AC_自动机(有点小题大作了))
//暴力,从每一行的开始处开始寻找要查询的字符#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 else39 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 }
2014 网选 5007 Post Robot(暴力或者AC_自动机(有点小题大作了))
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。