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;
}