首页 > 代码库 > bzoj 3059: 归途与征程
bzoj 3059: 归途与征程
Description
给出一个长度为N的由小写字母’a’~’z’和’*’组成的字符串A，一个长度为M的仅由小写字母’a’~’z’组成的字符串B。一个’*’可以匹配任意多个字符（包括0个）。求在B的所有循环同构串中，有多少个能够与A匹配。
循环同构串：就是把B的前k个字母(0<=k<M)移到结尾所得到的M个字符串。例如abc的循环同构串有abc、bca和cab。
A与B匹配：若除了A中的’*’号可以匹配B中的任意多个字符外，其余字符一一对应，则称A与B匹配。例如a*b*c与aadbc是匹配的，其中第一个*对应ad，第二个*对应空串。
Input
第一行为字符串A。
第二行为字符串B。
Output
输出在B的所有循环同构串中，有多少个能够与A匹配。
将B串倍长，将A串按通配符分割，分割后预处理每段在B串的匹配位置，枚举起始位置，强制要求A串首尾与起始、终止位置匹配，中间的段贪心取最左的，时间复杂度$O(nm)$
#include<cstdio>#include<cstring>char s1[107],s2[210007],*ss[107];int l1,l2,sp=0,ls[107];int nx[107][200007],ans=0;int main(){ scanf("%s%s",s1+1,s2+1); l1=strlen(s1+1); l2=strlen(s2+1); memcpy(s2+l2+1,s2+1,l2); s1[0]=s1[l1+1]=‘*‘; for(int i=1;i<=l1+1;++i)if(s1[i-1]==‘*‘){ ss[sp]=s1+i; while(ss[sp][ls[sp]]!=‘*‘)++ls[sp]; ++sp; } --sp; for(int i=0;i<=sp;++i){ nx[i][l2*2]=l2*2; for(int j=l2*2-1;j;--j){ nx[i][j]=memcmp(ss[i],s2+j,ls[i])?nx[i][j+1]:j; } } for(int i=1;i<=l2;++i){ int mx=i+l2-ls[sp]; if(mx>0&&nx[0][i]==i&&nx[sp][mx]==mx){ int w=i; for(int i=0;i<sp&&w<=mx;++i)w=nx[i][w]+ls[i]; ans+=(w<=mx); } } return printf("%d\n",ans),0;}
bzoj 3059: 归途与征程
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。