KMP-Martian Strings-CF149E

2023-10-14 06:40

文章标签 kmp strings martian cf149e

本文主要是介绍KMP-Martian Strings-CF149E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

KMP-Martian Strings-CF149E

题意：

$给定长度为n的母串s以及q个模式串p，计算这q个模式串当中，能够由s中的两个不重叠的连续子串拼接而成的数量。\\抽象地，即s[a,b]+s[c,d]=p，且1<=a<=b<c<=d<=n，这就对子串的顺序和长度产生了限制。$

$样例：\\输入：\\ABCBABA \\2 \\BAAB \\ABBA\\对第一个模式串而言AB的位置在BA的左侧，不满足条件。\\对第二个模式串，a=1,b=2,c=3,d=4或c=5,d=6均满足条件，因此有1个模式串满足条件。\\输出：1$

$数据范围：母串长度 n \in [2, 100000] ，模式串数量 q \in [1, 100] ，模式串长度 m \in [1, 1000] 。$

题解：

$对母串和模式串正向kmp求最大前缀的长度，反向kmp求最大前缀的长度，\\若两者长度之和大于等于模式串长度m，说明可行。$

$当然，要考虑最大前缀所在的位置，如样例 1 。$

具体落实：

$① 、用数组 l e n 来保存当前位置所能匹配的最大长度。 l e n [i] ： s 中前 i 个字符能够与 p 的最大匹配的长度。$

$② 、对模式串 p 求 N e x t 数组，再利用 k m p 将其与 s 进行匹配，同时计算出 l e n 数组。$

$③ 、将 s 与 p 翻转，再对翻转后的 p 求 N e x t 数组。$

$④、翻转后的p再与s进行匹配，同时计算是否满足条件。\\ \qquad设翻转后s匹配到位置i，p匹配到位置j，j同时也是当前匹配的后缀的长度,\\ \qquad对翻转之后的s而言，i之后的子串能够与p匹配成功的最大长度应为len[n-i]，\\ \qquad若j+len[n-j]>=m说明能够拼接成功。$

$如下图：$
在这里插入图片描述

$注意：\\①、由数据范围知道，两个子串的长度都应当大于0，即j与len[n-j]必须大于0。\\ \qquad因此，若模式串p的长度m=1，则无法满足条件。\\②、每处理完一个模式串p，要将s翻转回来。$

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int q,n,m,cnt;
char s[N],p[N];
int Next[1010],len[N];void get_next()
{for(int i=2,j=0;i<=m;i++){while(j&&p[i]!=p[j+1]) j=Next[j];if(p[i]==p[j+1]) j++;Next[i]=j;}
}void kmp()
{for(int i=1,j=0;i<=n;i++){while(j&&s[i]!=p[j+1]) j=Next[j];if(s[i]==p[j+1]) j++;len[i]=max(len[i-1],j);if(j==m) j=Next[j];}
}int main()
{scanf("%s",s+1);n=strlen(s+1);scanf("%d",&q);while(q--){memset(Next,0,sizeof(Next));memset(len,0,sizeof(len));scanf("%s",p+1);m=strlen(p+1);get_next();if(m==1) continue;kmp();reverse(s+1,s+1+n);reverse(p+1,p+1+m);get_next();for(int i=1,j=0;i<=n;i++){while(j&&s[i]!=p[j+1]) j=Next[j];if(s[i]==p[j+1]) j++;if(j&&len[n-i]&&j+len[n-i]>=m){cnt++;break;}if(j==m) j=Next[j];}reverse(s+1,s+1+n);}printf("%d\n",cnt);return 0;
}