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[],s2[],*ss[];

int l1,l2,sp=,ls[];

int nx[][],ans=;

int main(){

    scanf("%s%s",s1+,s2+);

    l1=strlen(s1+);

    l2=strlen(s2+);

    memcpy(s2+l2+,s2+,l2);

    s1[]=s1[l1+]='*';

    for(int i=;i<=l1+;++i)if(s1[i-]=='*'){

        ss[sp]=s1+i;

        while(ss[sp][ls[sp]]!='*')++ls[sp];

        ++sp;

    }

    --sp;

    for(int i=;i<=sp;++i){

        nx[i][l2*]=l2*;

        for(int j=l2*-;j;--j){

            nx[i][j]=memcmp(ss[i],s2+j,ls[i])?nx[i][j+]:j;

        }

    }

    for(int i=;i<=l2;++i){

        int mx=i+l2-ls[sp];

        if(mx>&&nx[][i]==i&&nx[sp][mx]==mx){

            int w=i;

            for(int i=;i<sp&&w<=mx;++i)w=nx[i][w]+ls[i];

            ans+=(w<=mx);

        }

    }

    return printf("%d\n",ans),;

}

巴特西

bzoj 3059: 归途与征程

Description

Input

Output

最新文章

热门文章