3427.归途与征程

Time Limits: 1000 ms Memory Limits: 131072 KB

Description

img

Input

第一行为字符串A。

第二行为字符串B。

Output

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

Sample Input

1
2
3
4
5
6
7
8
9
输入1:
aaaa
aaaa
输入2:
a*a
aaaaaa
输入3:
*a*b*c*
abacabadabacaba

Sample Output

1
2
3
4
5
6
输出1:
4
输出2:
6
输出3:
15

Data Constraint

对于30%的数据,M<=20;

对于80%的测试点,M<=200;

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;
unsigned long long k[110],hash[110],g[110],temp;
char a[110],b[200010];
int f[200010][52],e[110],len1,len2,l,w,ans,cd;
int main()
{
scanf("%s",a+1);
len1=strlen(a+1);
hash[0]=1;
for (int i=1;i<=len1;i++) {
hash[i]=hash[i-1]*13331;
}
for (int i=1;i<=len1;i++)
if (a[i]=='*')
{
if (i>1&&a[i-1]!='*')
{
k[++l]=temp;
e[l]=cd;
temp=cd=0;
}
}
else
{
temp+=(a[i]-'a'+1)*hash[cd++];
}
if (a[len1]!='*')
{
k[++l]=temp;
e[l]=cd;
temp=cd=0;
}
scanf("%s",b+1);
len2=strlen(b+1);
if (!l)
{
printf("%d",len2);
return 0;
}
for (int i=1;i<=len2;i++){
b[len2+i]=b[i];
}
for (int i=1;i<=l;i++) {
f[len2*2+1][i]=f[len2*2+2][i]=len2*2+1;
}
for (int i=len2*2;i;i--)
{
memset(g,-1,sizeof(g));
g[0]=0;
for (int j=0;j<len1;j++){
if (i+j<=2*len2){
g[j+1]=g[j]+(b[i+j]-'a'+1)*hash[j];
}
}
for (int j=1;j<=l;j++)
{
f[i][j]=f[i+1][j];
if (g[e[j]]==k[j]){
f[i][j]=i+e[j]-1;
}
}
}
int j,p;
for (int i=1;i<=len2;i++)
{
bool flag=true;
for (j=len1;j&&a[j]!='*';j--){
if (a[j]!=b[i+len2-1-(len1-j)]){
flag=false;
break;
}
}
if (flag==false||j==0&&len1!=len2) {
continue;
}
for (p=1,w=i;p<=l-(a[len1]!='*');p++)
{
if (p==1&&a[1]!='*'&&f[i][p]+1!=i+e[1]){
break;
}
w=f[w][p]+1;
}
if (p>l-(a[len1]!='*')&&w<=i+len2-(len1-j)){
ans++;
}
}
printf("%d",ans);
return 0;
}