/** 题目:zoj3228 Searching the String 链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3441 题意:给定一个长度为N(N <= 105)的目标串,然后再给定M(M <= 105)个长度不大于6的字符串, 问这些字符串在目标串的出现次数(分可重叠和不可重叠两种)。 题解:可以覆盖情况下,直接建立自动机求次数。注意可能出现类型相同以及字符串相同。所以用map标记; 不可以覆盖情况下,直接建立自动机,查询的时候维护当前查到的字符串上一次找到的位置lastpos. 如果lastpos+该子串长度<=pos那么可以ans++,以及更新lastpos=pos; find(),find2()两个函数分别处理可覆盖,不可覆盖情况。先统一处理可覆盖,然后清空自动机重新构建不可覆盖情况下的自动机。 AC自动机好文章:http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html */ //#include<bits/stdc++.h> #include<cstring> #include<cstdio> #include<iostream> #include<map> #include<algorithm> #include<queue> using namespace std; #define P pair<int,int> #define ms(x,y) memset(x,y,sizeof x) #define LL long long const int maxn = 1005; const int mod = 1e9+7; const int maxnode = 100000*6+10; const int sigma_size = 26; map<string,int> mp1, mp2; struct node { char s[7]; int type; int len; int ans; int lastpos; }t[100005]; struct AhoCorasickAutomata { int ch[maxnode][sigma_size]; int val[maxnode]; int sz; int f[maxnode]; int last[maxnode]; void clear(){sz = 1; memset(ch[0],0,sizeof ch[0]); } int idx(char c){return c-'a'; } void insert(char *s,int x) { int u = 0, n = strlen(s); for(int i = 0; i < n; i++){ int c = idx(s[i]); if(!ch[u][c]){ memset(ch[sz], 0, sizeof ch[sz]); val[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; } val[u] = x; } void find(char* T){ int j = 0; for(int i = 0; T[i]!='