1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map>10 using namespace std;11 12 const int maxn=1e5;13 const int MOD=1000000007;14 15 char a[maxn],b[maxn];16 int _next[maxn];17 int d[maxn];18 19 void get_next()20 {21     int i=-1,j=0;22     _next[0]=-1;23     while(j<strlen(b))24     {25         if(i==-1||b[i]==b[j])26             _next[++j]=++i;27         else28             i=_next[i];29     }30 }31 32 int KMP(int n,int m)33 {34     int i, j;35     i = j = 0;36     while (i<n)37     {38         if (j == -1 || a[i] == b[j])39         {40             if(i>0)  d[i]=d[i-1];41             i++;42             j++;43             if (j == m)  d[i-1]=(d[i-1-(j-1-_next[j-1])]+d[i-1-m]+1)%MOD;44         }45         else46             j = _next[j];47     }48 }49 50 51 int main()52 {53     //freopen("D:\\input.txt","r",stdin);54     int T;55     scanf("%d",&T);56     for(int kase=1;kase<=T;kase++)57     {58         scanf("%s",&a);59         scanf("%s",&b);60         int n=strlen(a); int m=strlen(b);61         memset(d,0,sizeof(d));62         get_next();63         KMP(n,m);64         printf("Case #%d: ",kase);65         printf("%d\n",d[n-1]+1);66     }67     return 0;68 }