首页 > 代码库 > 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_自动机(有点小题大作了))