admin 管理员组

文章数量: 887021

KMP

KMP-Martian Strings-CF149E

题意：

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

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

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

题解：

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

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

具体落实：

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

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

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

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

如 下 图 ： 如下图： 如下图：

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

本文标签： KMP

版权声明：本文标题：KMP 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/free/1699605058h368405.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。