jzoj 3427 归途与征程

本文主要是介绍jzoj 3427 归途与征程，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

第一行为字符串A。

第二行为字符串B。

Output

输出在B的所有循环同构串中，有多少个能够与A匹配。

Sample Input

输入1：

aaaa

aaaa

输入2：

a*a

aaaaaa

输入3：
*a*b*c
abacabadabacaba

Sample Output

输出1：

4

输出2：

6

输出3：

15

Data Constraint

对于30%的数据，M<=20；

对于80%的测试点，M<=200；

对于100%的测试点，1<=N<=100,1<=M<=100000。

---

Solution

对于循环同构串，直接复制1到m-1到B串后面
因为*号可以是任意字符，所以会把A串分成几个部分，只要这些部分按照顺序依次出现在B串中，就可以统计答案（不过要特判头尾不是*的部分)
用f[i][j]表示从B的第i为起点，能否匹配A的第j块
用next[i][j]不是从B的第i为起点，最近能匹配A的第j块的位置，这个可以由f得到
匹配可以使用kmp

---

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;#define N 111
#define M 100001int f[M*2][N/2],next[M*2][N/2];
int a[N],b[M*2],q[N],p[N],l[N];
int ans,n,m,t;
int i,j,k;void init()
{char c[M];scanf("%s\n",c);n=strlen(c);for (i=1;i<=n;i++)a[i]=int(c[i-1])-97;scanf("%s",c);m=strlen(c);for (i=1;i<=m;i++)b[i]=int(c[i-1])-97;for (i=m+1;i<=2*m-1;++i)b[i]=b[i-m];for (i=0;i<=25;++i)f[2*m][i]=2*m; memset(f,0,sizeof(f));  
}void kmp(int num,int mm)
{p[1]=0;int j=0;for (i=2;i<=mm;++i){while (j>0 && q[j+1]!=q[i]) j=p[j];if (q[j+1]==q[i]) j++;p[i]=j;}j=0;for (i=1;i<=2*m-1;++i){while (j>0 && q[j+1]!=b[i]) j=p[j];if (q[j+1]==b[i]) j++;if (j==mm) {f[i-mm+1][num]=1;j=p[j];}}
}void find()
{t=0;int i=1;while (i<=n){while (a[i]<0 && i<=n) i++;if (i>n) break;t++;l[t]=0;while (a[i]>=0 && i<=n){l[t]++;q[l[t]]=a[i];i++;}kmp(t,l[t]);}for (j=1;j<=t;++j){next[2*m][j]=m+m;for (i=2*m-1;i>=1;i--)if (f[i][j]==1) next[i][j]=i;else next[i][j]=next[i+1][j];}
}int main()
{//freopen("3427.in","r",stdin);//freopen("3427.out","w",stdout);init();find();ans=0;for (i=1;i<=m;++i){int ed=i+m-1;int now;now=next[i][1];if (now+l[1]-1>ed) continue;if (a[1]>=0 && now!=i) continue;int j; for (j=2;j<=t;++j)now=next[now+l[j-1]][j]; //printf("%d %d\n",now,ed);if (now+l[t]-1>ed || now==0) continue;if (a[n]>=0 && f[ed-l[t]+1][t]!=1) continue;ans++;}printf("%d\n",ans);return 0;
}

这篇关于jzoj 3427 归途与征程的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---