这个判断方法真的没想到。。。
对于在S中匹配M，如果M上一次的匹配位置pre与这一次的匹配位置now满足now-pre >= M.length，，则加1。
这个判断太跳了233。
#include <iostream>#include<time.h>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<string>#include<map>#include<vector>#include <algorithm>#include <queue>#include <cmath>#define LL long long#define ULL unsigned long longusing namespace std;const int MAXS = 26,MAXN = 600010;const int MATN = 70;struct MAT{int row,col;ULL mat[MATN][MATN];void Init(int R,int C,int val){row = R,col = C;for(int i = 1;i <= row; ++i)for(int j = 1;j <= col; ++j)mat[i][j] = (i == j ? val : 0);}MAT Multi(MAT c,LL MOD){MAT tmp;tmp.Init(this->row,c.col,0);int i,j,k;for(k = 1;k <= this->col; ++k)for(i = 1;i <= tmp.row; ++i)for(j = 1;j <= tmp.col; ++j)tmp.mat[i][j] += (this->mat[i][k]*c.mat[k][j]);return tmp;}MAT Quick(LL n,LL MOD){MAT res,tmp = *this;res.Init(row,col,1);while(n){if(n&1)res = res.Multi(tmp,MOD);tmp = tmp.Multi(tmp,MOD);n >>= 1;}return res;}void Output(){cout<<"****************"<<endl;int i,j;for(i = 1;i <= row; ++i){for(j = 1;j <= col; ++j)printf("%3lld ",mat[i][j]);puts("");}cout<<"&&&&&&&&&&&&&"<<endl;}};struct Trie{int next[MAXS];int fail;int flag;} st[MAXN];queue<int> q;int anw[100010];int pre[100010];struct QUERY{int y;char s[8];int len;}que[100100];struct ACautomaton{int Top,root;int Creat(){memset(st[Top].next,-1,sizeof(st[Top].next));st[Top].flag = 0;st[Top].fail = -1;return Top++;}void Init(){Top = 0;root = Creat();}inline int CalIndex(int c){return c-'a';}void Insert(char *s,int ty){int i = 0,tr = root,tmp;while(s[i] != '\0'){tmp = CalIndex(s[i]);if(st[tr].next[tmp] == -1)st[tr].next[tmp] = Creat();tr = st[tr].next[tmp],++i;}st[tr].flag = ty;}void GetFail(){st[root].fail = -1;q.push(root);int f,t;while(q.empty() == false){f = q.front();q.pop();for(int i = 0; i < MAXS; ++i){if(st[f].next[i] != -1){t = st[f].fail;while(t != -1 && st[t].next[i] == -1)t = st[t].fail;if(t == -1)st[st[f].next[i]].fail = root;elsest[st[f].next[i]].fail = st[t].next[i];q.push(st[f].next[i]);}}}}int OverLapMatch(char *s){int i ,tr = root,tmp;int ans = 0;for(i = 0; s[i] != '\0'; ++i){tmp = CalIndex(s[i]);while(tr != -1 && st[tr].next[tmp] == -1 )tr = st[tr].fail;if(tr == -1){tr = root;continue;}tr = st[tr].next[tmp];tmp = tr;while(tmp != root && st[tmp].flag != -1){if(st[tmp].flag)ans++,anw[st[tmp].flag]++;tmp = st[tmp].fail;}}return ans;}int NoOverLapMatch(char *s){int i ,tr = root,tmp;int ans = 0;for(i = 0; s[i] != '\0'; ++i){tmp = CalIndex(s[i]);while(tr != -1 && st[tr].next[tmp] == -1 )tr = st[tr].fail;if(tr == -1){tr = root;continue;}tr = st[tr].next[tmp];tmp = tr;while(tmp != root && st[tmp].flag != -1){if(st[tmp].flag){if(i-pre[st[tmp].flag] >= que[st[tmp].flag].len)ans++,anw[st[tmp].flag]++,pre[st[tmp].flag] = i;}tmp = st[tmp].fail;}}return ans;}};char s[100010];map<string,int> M;map<string,int>::iterator it;int main(){ // freopen("data1.in","r",stdin);int n,i;ACautomaton AC;int icase =1;while(scanf("%s",s) != EOF){scanf("%d",&n);for(i = 1;i <= n; ++i)scanf("%d %s",&que[i].y,que[i].s);for(i = 1;i <= n; ++i)que[i].len = strlen(que[i].s);memset(pre,-1,sizeof(pre));memset(anw,0,sizeof(anw));AC.Init();for(i = 1;i <= n; ++i){if(que[i].y == 0)AC.Insert(que[i].s,i);}AC.GetFail();AC.OverLapMatch(s);M.clear();for(i = n;i >= 1; –i){if(que[i].y == 0){it = M.find(que[i].s);if(it != M.end())anw[i] = anw[it->second];elseM.insert(pair<string,int>(que[i].s,i));}}AC.Init();for(i = 1;i <= n; ++i){if(que[i].y == 1)AC.Insert(que[i].s,i);}AC.GetFail();AC.NoOverLapMatch(s);M.clear();for(i = n;i >= 1; –i){if(que[i].y == 1){it = M.find(que[i].s);if(it != M.end())anw[i] = anw[it->second];elseM.insert(pair<string,int>(que[i].s,i));}}printf("Case %d\n",icase++);for(i = 1;i <= n; ++i)printf("%d\n",anw[i]);puts("");}return 0;}
回味起来却有久久不会退去的余香。
