本文主要是介绍zoj 3228 ac自动机，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给出一个字符串和若干个单词，问这些单词在字符串里面出现了多少次。单词前面为0表示这个单词可重叠出现，1为不可重叠出现。
Sample Input
ab
2
0 ab
1 ab
abababac
2
0 aba
1 aba
abcdefghijklmnopqrstuvwxyz
3
0 abc
1 def
1 jmn
Sample Output
Case 1
1
1
Case 2
3
2
Case 3
1
1
0
--------------------------------------------------
可重叠的很好处理，就是AC自动机处理。不可重叠的就记录下上次这个单词出现的位置，如果上次出现的位置加上这个单词的长度小于等于当前位置的话，那么这个单词的次数就加一。否则就不加。
int ans[100008*26][2] ;
int last[100008*26] ;
/*AC-------------*/
const int maxn = 100008 * 6 ;
const int kind = 26 ;
int next[maxn][kind] ;
int fail[maxn] ;
int deep[maxn] ;struct AC{int root , n ;int newnode(){for(int i = 0 ; i < kind ; i++) next[n][i] = -1 ;return n++ ;}void Init(){n = 0 ;root = newnode() ;deep[root] = 0 ;}int Insert(char *s , int indx){int now = root , k , len = strlen(s) ;for(int i = 0 ; i < len ; i++){k = s[i] - 'a' ;if(next[now][k] == -1){next[now][k] = newnode() ;deep[next[now][k]] = i + 1 ;}now = next[now][k] ;}return now ;}void makeAc(){queue<int> q ;fail[root] = root ;int now , i ;for(i = 0 ; i < kind ; i++){if(next[root][i] == -1)next[root][i] = root ;else{fail[next[root][i]] = root ;q.push(next[root][i]) ;}}while(! q.empty()){now = q.front() ; q.pop() ;for(i = 0 ; i < kind ; i++){if(next[now][i] == -1)next[now][i] = next[fail[now]][i] ;else{fail[next[now][i]] = next[fail[now]][i] ;q.push(next[now][i]) ;}}}}void ask(char *s){memset(ans , 0 , sizeof(ans)) ;memset(last , -1 , sizeof(last)) ;int now = root , len = strlen(s) ;for(int i = 0 ; i < len ; i++){int k = s[i] - 'a' ;now = next[now][k] ;int t = now ;while(t != root){ans[t][0]++ ;if(i - last[t] >= deep[t]){ans[t][1]++ ;last[t] = i ;}t = fail[t] ;}}}
}ac ;
/*EndAc---------------*/char word[8] ;
char text[100008] ;
int type[100008] ;
int pos[100008] ;int main(){int t , n , i , j , m , T = 1 ;while(scanf("%s" , text) != EOF){cin>> n ;ac.Init() ;for(i = 1 ; i <= n ; i++){scanf("%d%s" , &type[i] , word) ;pos[i] = ac.Insert(word , i) ;}ac.makeAc() ;ac.ask(text) ;printf("Case %d\n" , T++) ;for(i = 1 ; i <= n ; i++)printf("%d\n" , ans[pos[i]][type[i]]) ;puts("") ;}return 0 ;
}
这篇关于zoj 3228 ac自动机的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
