题目链接: https://cn.vjudge.net/contest/281961#problem/D
题目大意: 给你一个模式串, 然后给你多个匹配串, 匹配串的类型是包括可以覆盖的以及不可覆盖的.
具体思路: 对于可以覆盖的字符串, 我们就按照以前的方法来就行了, 对于不可以覆盖的字符串, 我们通过两个数组, 一个是 last 和 pos 数组, 对于不可覆盖的, 当前字符位置 - last[当前节点] <= pos[当前节点].last 数组记录的是当前这个字符串上次出现的位置.
AC 代码:
- #include<iostream>
- #include<stack>
- #include<stdio.h>
- #include<cstring>
- #include<string>
- #include<cmath>
- #include<queue>
- #include<algorithm>
- using namespace std;
- # define ll long long
- const int maxn = 2e5+50000;
- const int maxm = 1e6+100;
- char str1[maxn],str2[maxn];
- int tot,ch[maxn][30];
- int type[maxn],pos[maxn],node[maxn],val[maxn];
- int fail[maxn],last[maxn],ans[maxn][2];
- void add(int t)
- {
- int p=0;
- int len=strlen(str2);
- for(int i=0; i<len; i++)
- {
- int u=str2[i]-'a';
- if(!ch[p][u])
- ch[p][u]=++tot;
- p=ch[p][u];
- pos[p]=i+1;
- }
- node[t]=p;
- val[p]=1;
- }
- void getfail()
- {
- queue<int>q;
- for(int i=0; i<26; i++)
- {
- if(ch[0][i])
- q.push(ch[0][i]);
- }
- while(!q.empty())
- {
- int top=q.front();
- q.pop();
- for(int i=0; i<26; i++)
- {
- int u=ch[top][i];
- if(u==0)
- continue;
- q.push(u);
- int v=fail[top];
- while(v&&ch[v][i]==0)
- v=fail[v];
- fail[u]=ch[v][i];
- // last[u]=val[fail[u]] ? fail[u] : last[fail[u]];
- }
- }
- }
- void cal(int t,int i)
- {
- while(t)
- {
- ans[t][0]++;
- // cout<<i<<""<<last[t]<<" "<<pos[t]<<endl;
- if(i-last[t]>=pos[t])ans[t][1]++,last[t]=i;
- t=fail[t];
- // break;
- }
- }
- void getans()
- {
- memset(last,-1,sizeof(last));
- int len=strlen(str1);
- int p=0;
- for(int i=0; i<len; i++)
- {
- int u=str1[i]-'a';
- while(p&&ch[p][u]==0)
- p=fail[p];
- p=ch[p][u];
- if(val[p])
- cal(p,i);
- else if(fail[p])
- cal(fail[p],i);
- }
- }
- void init(){
- tot=0;
- memset(ch,0,sizeof(ch));
- memset(val,0,sizeof(val));
- memset(fail,0,sizeof(fail));
- memset(last,0,sizeof(last));
- memset(ans,0,sizeof(ans));
- }
- int main()
- {
- // memset(last,-1,sizeof(last));
- int n;
- int Case=0;
- while(~scanf("%s",str1))
- {
- init();
- scanf("%d",&n);
- for(int i=0; i<n; i++)
- {
- scanf("%d %s",&type[i],str2);
- add(i);
- }
- getfail();
- getans();
- printf("Case %d\n",++Case);
- for(int i=0; i<n; i++)
- {
- // cout<<node[i]<<" "<<type[i]<<endl;
- printf("%d\n",ans[node[i]][type[i]]);
- }
- printf("\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2948314.html