题目链接 1026CSUSTOJ
假设T串中组成为 S*** S **** S *****S
那么方案数是Cm1 +Cm2 KMP计算S在T中出现的次数即可
int nexts[1000005];int al,bl,rnm=0;char s,a[1000005],b[1000005];void getnext(){int p=0;nexts[1]=0;for(int i=2;i<=bl;i++){while(p&&b[i]!=b[p+1]) p=nexts[p];if(b[p+1]==b[i]) p++;nexts[i]=p;}return;}ll op=0;void KMP(){int p=0;for(int i=1;i<=al;i++){while(p&&b[p+1]!=a[i]) p=nexts[p];if(b[p+1]==a[i]) p++;if(p==bl){//相等 i-bl+1 匹配到的位置op++;p=nexts[p];}}return;}signed main(){while(scanf("%s%s",b+1,a+1)!=EOF){op=0;al=strlen(a+1);bl=strlen(b+1);getnext();KMP();printf("%lld\n",(op*(op-1))/2+op);}}
如果觉得《CSUSTOJ 1026 ST（KMP）》对你有帮助，请点赞、收藏，并留下你的观点哦！
