CSUSTOJ 1026 ST（KMP）

题目链接 1026CSUSTOJ

假设T串中组成为 S*** S **** S *****S
那么方案数是C_m¹ +C_m² 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);
}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！