526互联

CF149E Martian Strings 题解

发布时间 2023-06-07 11:16:02作者: frostwood

题意

给定一个主串 \(s\) 和一些模式串 \(p_i\)，问主串中是否存在两个不相交的非空字串，拼起来和模式串相同。

考虑如何拼接 \(p_i\)。我们可以从前向后匹配一遍主串，找到 \(p_i\) 的所有长度的前缀在主串中最先出现的位置，并记录下来；然后再从后向前跑匹配，每次匹配上一个后缀，就判断该后缀在主串中的起始位置是否大于这一后缀对应前缀的结束位置，如果是则答案加一。注意判断边界条件。匹配这里用的是KMP算法。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;

char b[N], s[N];
int n, m, lth;
int fnxt[N], bnxt[N], posl[1005], posr[1005];
bool KMP(){
    int j = 0;
    for(int i = 2; i<=lth; i++){
        while(j && b[j+1]!=b[i]){
            j = fnxt[j];
        }
        if(b[j+1]==b[i]){
            j++;
        }
        fnxt[i] = j;
    }
    j = lth+1;bnxt[lth] = lth+1;
    for(int i = lth-1; i>=1; i--){
        while(j<=lth&&b[j-1]!=b[i]){
            j = bnxt[j];
        }
        if(b[j-1]==b[i]){//只记录第一次出现的结束位置
            j--;
        }
        bnxt[i] = j;
    }
    memset(posl, 0, sizeof(posl));
    j = 0;
    for(int i = 1; i<=n; i++){
        while(j && s[i]!=b[j+1]){
            j = fnxt[j];
        }
        if(s[i]==b[j+1]){
            j++;
        }
        if(!posl[j]&&j){
            posl[j] = i;
        }
    }
    j = lth+1;
    
    for(int i = n; i>=1; i--){
        while(j<=lth&&b[j-1]!=s[i]){
            j = bnxt[j];
        }
        if(s[i]==b[j-1]){
            j--;
        }
        if((j-1)&&posl[j-1]&&posl[j-1]<i&&(j<=lth)){//注意前后缀都要非空
            return true;
        }
    }
    return false;
}
int ans;
int main(){
    scanf("%s", s+1);
    n = strlen(s+1);
    scanf("%d", &m);
    while(m--){
        scanf("%s", b+1);
        lth = strlen(b+1);
        if(KMP()){
            ans++;
        }
    }
    printf("%d\n", ans);
    system("pause");
    return 0;
}