网站建设 广州网站建设专业公司,什么腾讯网站做任务能刷q币,建设银行重大新闻,企业网站托管运营KMP算法
全称Knuth-Morris-Pratt算法#xff0c;是一种字符串匹配算法。该算法的目的是在一个文本串S内查找一个模式串P的出现位置。
KMP算法的核心思想是利用模式串自身的特性来避免不必要的字符比较。算法通过构建一个部分匹配表#xff08;也称为next数组#xff09;是一种字符串匹配算法。该算法的目的是在一个文本串S内查找一个模式串P的出现位置。
KMP算法的核心思想是利用模式串自身的特性来避免不必要的字符比较。算法通过构建一个部分匹配表也称为next数组来记录模式串中每个字符之前的前缀子串和后缀子串的最长公共长度。根据这个表算法可以通过调整模式串的起始位置来跳过不需要比较的字符从而提高匹配的效率。
KMP算法的具体步骤如下
1. 预处理模式串P构建部分匹配表next数组 2. 设置两个指针i和j分别指向文本串S和模式串P的起始位置 3. 逐个比较S[i]和P[j]如果相等则i和j同时后移 4. 如果不相等根据next数组跳过一部分字符将j更新为next[j]同时i保持不变 5. 重复步骤3和步骤4直到找到一个匹配或者S已经遍历完。
KMP算法的时间复杂度为O(mn)其中m和n分别是文本串和模式串的长度。相比于暴力匹配算法的时间复杂度O(m*n)KMP算法能够在较短的时间内找到匹配位置。
题目描述
给出两个字符串 s1 和 s2若 s1 的区间 [l,r] 子串与 s2 完全相同则称 s2 在 s1 中出现了其出现位置为 l。 现在请你求出 s2 在 s1 中所有出现的位置。
定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串 t满足 t 既是 s 的前缀又是 s 的后缀。 对于 s2你还需要求出对于其每个前缀 s′ 的最长 border t′ 的长度。
输入格式
第一行为一个字符串即为 s1。 第二行为一个字符串即为 s2。
输出格式
首先输出若干行每行一个整数按从小到大的顺序输出 s2 在 s1 中出现的位置。 最后一行输出 ∣s2∣ 个整数第 i 个整数表示 s2 的长度为 i 的前缀的最长 border 长度。
输入输出样例
输入 #1复制
ABABABC ABA
输出 #1复制
1 3 0 0 1
说明/提示
样例 1 解释
。
对于 s2 长度为 3 的前缀 ABA字符串 A 既是其后缀也是其前缀且是最长的因此最长 border 长度为 1。
数据规模与约定
本题采用多测试点捆绑测试共有 3 个子任务。
Subtask 130 points∣s1∣≤15∣s2∣≤5。
Subtask 240 points∣s1∣≤10^4∣s2∣≤10^2。
Subtask 330 points无特殊约定。
对于全部的测试点保证 1≤∣s1∣,∣s2∣≤10^6s1,s2 中均只含大写英文字母。
#includestdio.h
#includestring.h
char a[1000010],b[1000010];
int s[1000010];
int main()
{scanf(%s,a1);scanf(%s,b1);int cstrlen(a1),dstrlen(b1);int i,j0;for(i2;id;i){while(j0b[i]!b[j1]) js[j];if(b[i]b[j1]) j;s[i]j;}j0;for(i1;ic;i){while(j0a[i]!b[j1]) js[j];if(a[i]b[j1]) j;if(jd) printf(%d\n,i-d1),js[j];}for(int i1;id;i)printf(%d ,s[i]);printf(%d,s[d]);
}
