学习报告：kmp

建站1510 更新时间：2025-06-08 06:05:14

学习报告：kmp

我们应该都知道一个这样子的题目，

输入两个字符串，求一个字符串在另一个字符串出现的次数，我们可以使用两个for循环来解决这个事，可是这个方法的时间要太久了，所以就需要我们kmp，我们先来介绍一个表

这个表的原理就是我们可以通过他找到上一次出现的下标，首先我们看这个字符串

将它拆成这样子，就是a，ab~~~这样子我画图不太行，不过我相信聪明的你肯定看的懂

然后我们找每一个的最长相等的前后缀，将他和数组下标一一对应，不得不说他们画的真好

这样子我们就可以得到每个下标的前后缀，然后就是我们最后那个数不要，然后一个下标对于一个数，就像这样子

然后，我们再去找一一对应的关系

当我们没有对于上的时候，我们就将j（p的下标）到我们刚刚那个表也就是最下面那个数字的下标，j=1，然后再进行对比，这样子，我们的对应速度就会快很多，有可能这个不明显那我们换成

用上面这个方法是不是快多了！这些就是kmp的思想，那我们要怎么代码实现呢，首先我们要把那个表搞出来，这个表搞出来，这个有一步：

      else{if(len>0){len=table[len-1];}else{next[i]=table[i]=len;i++;}}

这一步我也不太懂，可以看看这个大佬讲的

【KMP字符串匹配算法2】

=c9016f395efdf6f1094ae706e81044e3

void table1(char arr[],int n)
{int i,len;n=strlen(arr);next[i]=table[0]=0;//table表示表len=0;//用来记录我们的表中的数i=1;while(i<n){if(arr[i]==arr[len]){len++;next[i]=table[i]=len;i++;}else{if(len>0){len=table[len-1];}else{next[i]=table[i]=len;i++;}}}
}

然后我们找出来这个表，把他往后移一位，将第一个数改成-1，这样子方便我们下面判断，你要是要改为666也没关系，你只能祈祷数据不会加到666去

void movetable(int n)
{int i;for(i=n-1;i>0;i--){table[i]=table[i-1];}table[0]=-1;
}

做完上面准备步骤，下面就是找相同啦

void zhao(char arr[],char brr[])
{int i,j,n,m;//brr为子串，arr为主串n=strlen(brr);//brr的jm=strlen(arr);//arr的ii=j=0;table1(brr,n);movetable(n);while(i<m){if(j==n-1&&arr[i]==brr[j]){printf("%d\n",i-j+1);j=table[j];//这步就是我们可以如果ababa  aba你要是直接等于0就错了，我们要回到上一次出现的地方，然后继续找}if(arr[i]==brr[j]){i++;j++;}else{j=table[j];//不相等我们就让brr下标的移到他上一次出现的地方if(j==-1)//找到最后啦，就说明找不到，找不到就拉到，重新开始找呗{i++;j++; }}}
}

这上面就是kmp的算法思想以及我们的代码实现，写个题目吧

复制Markdown 展开

题目描述

给出两个字符串 s_1s1 和 s_2s2，若 s_1s1 的区间 [l, r][l,r] 子串与 s_2s2 完全相同，则称 s_2s2 在 s_1s1 中出现了，其出现位置为 ll。

现在请你求出 s_2s2 在 s_1s1 中所有出现的位置。

定义一个字符串 ss 的 border 为 ss 的一个非 ss 本身的子串 tt，满足 tt 既是 ss 的前缀，又是 ss 的后缀。

对于 s_2s2，你还需要求出对于其每个前缀 s's′ 的最长 border t't′ 的长度。

输入格式

第一行为一个字符串，即为 s_1s1。

第二行为一个字符串，即为 s_2s2。

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 s_2s2 在 s_1s1 中出现的位置。

最后一行输出 |s_2|∣s2∣ 个整数，第 ii 个整数表示 s_2s2 的长度为 ii 的前缀的最长 border 长度。

输入输出样例

输入 #1复制

ABABABC

ABA

输出 #1复制

1

3

0 0 1

说明/提示

样例 1 解释

。

对于 s_2s2 长度为 33 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 11。

数据规模与约定

本题采用多测试点捆绑测试，共有 3 个子任务。

Subtask 1（30 points）：|s_1| \leq 15∣s1∣≤15，|s_2| \leq 5∣s2∣≤5。

Subtask 2（40 points）：|s_1| \leq 10^4∣s1∣≤104，|s_2| \leq 10^2∣s2∣≤102。

Subtask 3（30 points）：无特殊约定。

对于全部的测试点，保证 1 \leq |s_1|,|s_2| \leq 10^61≤∣s1∣,∣s2∣≤106，s_1, s_2s1,s2 中均只含大写英文字母。

这个题目简简单单，没什么好说的就是我们找出他的位置，然后还要输出一下表格，注意一下，我们找的表格不是移动后的是移动前的，所以我们就再加个表格记录一下呗，值得注意的是这个数组一定一定要大！！！要不然得不到100！！！

#include <stdio.h>
#include <string.h>
#define MAXN 1000010
int table[MAXN];
int next[MAXN];
char arr[MAXN];
char brr[MAXN];
void table1(char arr[],int n)
{int i,len;n=strlen(arr);next[i]=table[0]=0;//table表示表len=0;//用来记录我们的表中的数i=1;while(i<n){if(arr[i]==arr[len]){len++;next[i]=table[i]=len;i++;}else{if(len>0){len=table[len-1];}else{next[i]=table[i]=len;i++;}}}
}void movetable(int n)
{int i;for(i=n-1;i>0;i--){table[i]=table[i-1];}table[0]=-1;
}void zhao(char arr[],char brr[])
{int i,j,n,m;//brr为子串，arr为主串n=strlen(brr);//brr的jm=strlen(arr);//arr的ii=j=0;table1(brr,n);movetable(n);while(i<m){if(j==n-1&&arr[i]==brr[j]){printf("%d\n",i-j+1);j=table[j];//这步就是我们可以如果ababa  aba你要是直接等于0就错了，我们要回到上一次出现的地方，然后继续找}if(arr[i]==brr[j]){i++;j++;}else{j=table[j];//不相等我们就让brr下标的移到他上一次出现的地方if(j==-1)//找到最后啦，就说明找不到，找不到就拉到，重新开始找呗{i++;j++; }}}
}int main()
{scanf("%s",arr);scanf("%s",brr);zhao(arr,brr);int n=strlen(brr);for(int i=0;i<n;i++){printf("%d ",next[i]);}return 0;
}

下班！明天学另一个，加油加油加油！