题目
分析
好吧。。。明显是暴力题。
首先，把A串分成只有小写字母组成的小分串，按顺序存放：A[1]、A[2]、A[3]……。 对于同构循环串，显然把两个B串合在一起，成为一个新的C串。\(C[i...i+m-1]\)(1<=i<=|B|)就是一个同构循环串。 接着设\(f[i][j]\)指在\(C[i+1...|C|]\)中第一个A[j]的位置，可以用kmp求出来。 然后就可以愉愉快快得暴力啦！ 暴力：对于一个同构循环串\(C[i...i+|B|-1]\)，设k=i-1，每次k调到下一个A的小分串的结尾（即k=f[k][j]+len[j]-1(当前做到的是第j个小分串)），当k>i+|B|-1,那么就是说在\(C[i...i+|B|-1]\)中没有对应的A串，break。 注意判断A串的开头结尾不是‘*’的情况。开头情况的：如果\(f[0][1]<>1\)就continue。结尾一样。#include#include #include #include #include #include #include const int maxlongint=2147483647;using namespace std;char sm[210000],sn[110][110];int n,m,ans,tot,pos[110],len[110],tt,f[200500][102];int next[110];int kmp(int x){ memset(next,0,sizeof(next)); int j=0; for(int i=2;i<=len[x];i++) { while(j>0 && sn[x][i]!=sn[x][j+1]) j=next[j]; if(sn[x][i]==sn[x][j+1]) j++; next[i]=j; } j=0; for(int i=1;i<=2*m;i++) { while(j>0 && sm[i]!=sn[x][j+1]) j=next[j]; if(sm[i]==sn[x][j+1]) j++; if(j==len[x]) { f[i-j+1-1][x]=i-j+1; } }}int main(){ scanf("%s\n%s\n",sn[0]+1,sm+1); n=strlen(sn[0]+1); m=strlen(sm+1); for(int i=1;i<=m;i++) { sm[m+i]=sm[i]; } for(int i=1;i<=n;i++) { if(sn[0][i]!='*') { pos[++tot]=i; len[tot]=0; while(sn[0][len[tot]+1+pos[tot]-1]!='*' && len[tot]+1+pos[tot]-1<=n) { sn[tot][++len[tot]]=sn[0][len[tot]+pos[tot]-1]; } i=len[tot]+pos[tot]-1; } } for(int j=1;j<=tot;j++) kmp(j); for(int i=2*m;i>=0;i--) { for(int j=1;j<=tot;j++) { if(!f[i+1][j]) f[i+1][j]=maxlongint/5; if(!f[i][j]) { f[i][j]=f[i+1][j]; } } } for(int i=1;i<=m;i++) { if(sn[0][1]!='*') { if(f[i-1][1]!=i) continue; } if(sn[0][n]!='*') { if(f[i+m-1-len[tot]+1-1][tot]!=i+m-1-len[tot]+1) continue; } int k=i-1; for(int j=1;j<=tot;j++) { k=f[k][j]+len[j]-1; if(k>i+m-1) { ans--; break; } } ans++; } printf("%d",ans);}