KMP算法中next数组的构建
2024-08-27 01:58:51
记得初学$kmp$的时候 老师让大家把它直接背下来
然而不理解的话 不仅调试起来比较慢 很多题目也难往$kmp$上想
-----------------------------------------------------------------------
设字符串为$s$ 长度为$len$ 起始位置为$1$
首先要明白的就是 next数组的意思 便是$s[$从 $1$ 到$ i]$的后缀与$s[$从 $1$到 $i -1]$的前缀的最长公共部分长度
$($假设为$k$,则$s[$从$ 1$ 到$ i]$与$s[$从$i - k$ 到 $i - 1]$匹配$)$
此处可参见NOI2014动物园的题目描述$($只用看题目描述里对$next$数组的解释便可 题目无需思考$)$
于是我们便可以开始构建$next$数组了
#include <bits/stdc++.h>
using namespace std;
const int N = ;
char s[N];
int next[N];
int len;
int main()
{
scanf("%s",s + );
len = strlen(s + );
next[] = ;
int j = ;
for(int i = ;i <= len; ++i)
{
while(j && s[i] != s[j + ])j = next[j];
//不断向前寻找 直到s[从1到i]的后缀与s[从1到j+1]匹配
//之所以j=next[j]的原因是s[从1到j]的后缀与s[从1到next[j]]匹配
//不同的只是s[j+1]与s[next[j]+1] 这一点也可以解释为何只需最后一位匹配
if(s[i] == s[j + ])
next[i] = ++j;
//若匹配成功 则最长公共部分长度为n+1
else
next[i] = ;
//否则 无公共部分
}
for(int i = ;i <= len; ++i)
printf("%d ", next[i]);
}
自认为字符串下标从$1$开始 比从$0$开始 使人更易理解$next$数组的含义$($然而大部分$kmp$模板中字符串下标都是从$0$开始的$)$
最新文章
- mysql代码执行漏洞
- Django Restful Framework (二): ModelSerializer
- ComboBox,三级联动菜单,新入门点小白,有些代码有待优化,大神勿喷
- 再见,OI
- Javascript本质第一篇:核心概念
- NET Core HTTP 管道
- Selenium2+python自动化14-iframe
- (转)javaScript插件开发
- DTCMS列表页自定义参数。
- 电脑问题交流QQ群
- mysql设置指定ip远程访问连接实例
- 【安全】requests和BeautifulSoup小试牛刀
- Smarty 保留变量
- MySQLdb-python的安装
- Dynamics 365 Online-Virtual Entities
- 记录常用的adb命令
- jquery追加元素的不同语法
- Javascript-短路 与(&;&;)
- sqlserver 存入DB中的中文乱码
- win10无法访问samba共享