Codeforces 149E

传送门：Codeforces 149E

题意

给定一个主串S（长度为n）以及t个模式串P（长度为m），问有多少个模式串，可以由主串中的左右两个模式串拼成。

题解

首先枚举划分母串的位置i，左边是S[1~i]，右边是S[i+1,n]。那么，假设“左边”和“子串P的前缀”的最长匹配长度为len1，“右边”和“子串P的后缀”的最长匹配长度为len2，如果len1+len2>=m，说明能够拼成模式串。
kmp算法中f[i]表示“母串S以i结尾的后缀”和“子串P的前缀”的能够匹配的最长长度，那么len1就等于f[1~i]中的最大值。同理，翻转主串和模式串再跑一次kmp就可以求出len2。

注

1、当模式串长度为1时，直接跳过，因为不能由两个串拼成。
2、 不要一直调用strlen，定义全局变量或传参，T了好几发，落泪。
3、 做完一个模式串之后再把主串翻转回来。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
char a[N],b[N];
int f[2][N],nxt[2][N];
int n,ans,la,lb;

void getnxt(char *p,int k){
    nxt[k][1]=0;
    for(int i=2,j=0;i<=lb;i++){
        while(j>0&&p[i]!=p[j+1]) j=nxt[k][j];
        if(p[i]==p[j+1]) j++;
        nxt[k][i]=j;
    }
}

void kmp(char *s,char *p,int k){
    for(int i=1,j=0;i<=la;i++){
        while(j>0&&(j==lb||s[i]!=p[j+1])) j=nxt[k][j];
        if(s[i]==p[j+1]) j++;
        f[k][i]=j;
    }
}

int main(){
    scanf("%s",a+1);
    scanf("%d",&n);
    la=strlen(a+1);
    for(int i=1;i<=n;i++){
        scanf("%s",b+1);
        lb=strlen(b+1); 
        if(lb==1) continue;
        getnxt(b,0);
        kmp(a,b,0);
    
        reverse(a+1,a+la+1);
        reverse(b+1,b+lb+1);
    
        getnxt(b,1);
        kmp(a,b,1);

        for(int i=1;i<=la;i++){
            f[0][i]=max(f[0][i-1],f[0][i]);
            f[1][i]=max(f[1][i-1],f[1][i]);
        }
        bool flag=0;
        for(int i=1;i<la;i++){
            int j=la-i;
            if(!f[0][i]||!f[1][j]) continue;
            if(f[0][i]+f[1][j]>=lb){
                flag=1;
                break;
            }
        }
        if(flag) ans++;
        reverse(a+1,a+la+1); 
    }
    printf("%d\n",ans);
    return 0;
}

Codeforces 149E

原文：https://www.cnblogs.com/qjy73/p/12459283.html