首页 > 其他 > 详细

Codeforces 149E

时间:2020-03-10 23:40:55      阅读:68      评论:0      收藏:0      [点我收藏+]

传送门: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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!