前缀函数及kmp算法1、字符串基础2、前缀函数3、应用

80 阅读 0 评论 53 点赞

我是靠谱客的博主阳光芒果，最近开发中收集的这篇文章主要介绍前缀函数及kmp算法1、字符串基础2、前缀函数3、应用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1、字符串基础

1.1 字符集

一个字符集 $sum$ 是一个建立了全序关系的集合，也就是说 $sum$ 中的任意两个不两只的元素 $alpha$ 和 $beta$ 都可以比较大小，要么 $alpha < beta$ ,要么 $beta < alpha$ 。字符集 $sum$ 中的元素称为字符。

1.2 字符串

一个字符串S是将n个字符顺次排列形成的序列，n称为S的长度，表示为 $|s|$ 。S的第i个字符表示为S[i]。

1.3 子串

字符串S的子串S[i..j]， $i leq j$ ，表示S串中从i到j这一段，也就是顺次排列S[i], S[i+1],...,S[j]形成的字符串。

1.4 子序列

字符串S的子序列是从S中将若干元素提取出来并不改变相对位置形成的序列，即 $s[p_1],s[p_2],...,s[p_k]$ ， $1 textless p_1 textless p_2 textless cdots textless p_k leq |s|$

1.5 后缀

后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串S的从i开头的后缀表示为Suffix(S,i)，也就是Suffix(S,i) = S[i..|S|-1]。

真后缀指除了S本身的S的后缀。

举例来说，字符串 abcabcd 的所有后缀为 {d, cd, bcd, abcd, cabcd, bcabcd, abcabcd}，而它的真后缀为 {d, cd, bcd, abcd, cabcd, bcabcd}。

1.6 前缀

前缀是指从串首开始到某个位置i结束的一个特殊子串。字符串S的以i结尾的前缀表示为Prefix(S,i)，也就是Prefix(S,i)=S[0..i]。

真前缀指除了S本身的S的前缀。

举例来说，字符串 abcabcd 的所有前缀为 {a, ab, abc, abca, abcab, abcabc, abcabcd}, 而它的真前缀为 {a, ab, abc, abca, abcab, abcabc}。

1.7 字典序

以第i个字符作为第i关键字进行大小比较，空字符小于字符集内任何字符(即 $a textless aa$ ）

1.8 回文串

回文串是正着写和倒着写相同的字符串。即满足 $forall 1 leq i leq |s|,s[i] =s[|s| + 1 - i]$ 的s。

2、前缀函数

给定一个长度为n的字符串s，其前缀函数被定义为一个长度为n的数组 $pi$ 。其中 $pi[i]$ 的定义是

如果子串s[0..i]有一对相等的真前缀与真后缀：s[0...k-1]和s[i-(k-1)...i]，那么 $pi[i]$ 就是这个相等的真前缀的长度，也就是 $pi[i]=k$
如果不止有一对相等的，那么 $pi[i]$ 就是其中最长的那一对的长度。
如果没有相等的，那么 $pi[i]=0$

简单来说 $pi[i]$ 就是子串s[0...i]最长的相等的真前缀与真后缀的长度。

有数学语言描述如下

$pi[i]=max limits_{k=0...i}{k=s[0..k-1]=s[i-(k-1)...i]}$

特别地，规定 $pi[0]=0$

2.1 朴素算法

按照定义计算前缀函数的算法流程

在一个循环中以 $i=1rightarrow n-1$ 的顺序计算前缀函数 $pi[i]$ 的值( $pi[0]=0$ )
为了计算当前的前缀函数值 $pi[i]$ ，令变量j从最大的真前缀长度i开始尝试。
如果当前长度下真前缀与真后缀相等，则此时长度为 $pi[i]$ ,否则令j自减1，继续匹配，直到 $j=0$
如果 $j=0$ 并且仍没有任何一次匹配，则置 $pi[i]$ =0，并移至下一个下标 $i+1$

实现如下：

vector<int> prefix_function(string s) {
int n = (int)s.length();
vector<int> pi(n);
for (int i = 1; i < n; i++)
for (int j = i; j >= 0; j--)
if (s.substr(0, j) == s.substr(i - j + 1, j)) {
pi[i] = j;
break;
}
return pi;
}

2.2 优化算法一

基于相邻的前缀函数值至多增加1。

当相邻前缀函数值增加时，即 $pi[i+1]$ 比 $pi[i]$ 多1时，满足 $s[i+1]=s[pi[i]]$ 。所以当移到到下一个位置时，前缀函数的值要么增加1，要么维持不变，要么减少。

改进算法为

vector<int> prefix_function(string s) {
int n = (int)s.length();
vector<int> pi(n);
for (int i = 1; i < n; i++)
for (int j = pi[i - 1] + 1; j >= 0; j--)
// improved: j=i => j=pi[i-1]+1
if (s.substr(0, j) == s.substr(i - j + 1, j)) {
pi[i] = j;
break;
}
return pi;
}

2.3 优化算法二

当 $s[i+1] neq s[pi[i]]$ 时

失配时，对于子串s[0...i]，仅次于 $pi[i]$ 的第二长度j，使得在位置i的前缀性质仍得以保持，即 $s[0...j-1]=s[i-j+1...i]$ 。如果找到了这样的长度j,那么仅需要再次比较s[i+1]和s[j]。如果它们相等，那么有 $pi[i+1]=j+1$ 。否则，需要找到子串s[0...i]仅次于j的第二长度 $j^{(2)}$ ，使得前缀性质得以保持，如此反复，直到j=0。如果 $s[i+1] neq s[0]$ ，则 $pi[i+1] = 0$ 。

对于第二长度j，因为 $s[0...pi[i]-1]=s[i-pi[i]+1...i]$ ，有 $s[0..j-1]=s[i-j+1...i]=s[pi[i]-j...pi[i]-1]$ 。也就是说j等价于子串 $s[pi[i]-1]$ 的前缀函数值，即 $j=pi[pi[i]-1]$ 。同理将于j的第二长度等价于s[j-1]的前缀函数值，即 $j^{2}=pi[j - 1]$ 。关于j的状态转移方法为 $j^{n}=pi[j^{n-1}-1]$ , $j^{n-1} textgreater 0$

改进算法为：

vector<int> prefix_function(string s) {
int n = (int)s.length();
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) j = pi[j - 1];
if (s[i] == s[j]) j++;
pi[i] = j;
}
return pi;
}

3、应用

3.1 字符串周期

对于字符串s和 $0 textless p leq |s|$ ，若s[i] = s[i+p]对所有 $i in left[0, |s| - p - 1 right ]$ 成立，则称p为s的周期。

对于字符串s和 $0 le r textless |s|$ ，若s长度为r的前缀和长度为r的后缀相等，就称s长度为r的前缀是s的border，则|s|-r是s的周期。

3.2 字符串查找

在文本串与模式串匹配时，使用前缀函数，代码如下

private boolean kmpSearch(String pattern, String text, int[] pi) {
int textLen = text.length();
int patternLen = pattern.length();
int ans = 0;
int j = 0;
for (int i = 0; i < textLen; i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = pi[j - 1];
}
if (pattern.charAt(j) == text.charAt(i)) {
j++;
}
if (j == patternLen) {
return true;
}
}
return false;
}

另外一种解法是构造s+#+t的串，计算其前缀函数，判断|s|+1到|s|+1+|t|之间的前缀函数值是否等于模式串的长度。

3.3 构造自动机

先计算前缀函数，根据字符集构造自动机

private int[][] computeAutomation(String pattern) {
int n = pattern.length();
int[][] aut = new int[n][N];
int[] pi = prefixFunction(pattern);
for (int i = 0; i < n; i++) {
for (int j = 0; j < N; j++) {
if (i > 0 && 'a' + j != pattern.charAt(i)) {
aut[i][j] = aut[pi[i - 1]][j];
} else {
aut[i][j] = i + (pattern.charAt(i) == 'a' + j ? 1 : 0);
}
}
}
return aut;
}

3.4 前缀统计

根据前缀函数计算

int n = pattern.length();
int[] cnt = new int[n + 1];
int[] pi = prefixFunction(pattern);
for (int i = 0; i < n; i++) {
cnt[pi[i]]++;
}
for (int i = n - 1; i > 0; i--) {
cnt[pi[i - 1]] += cnt[i];
}
for (int i = 0; i <= n; i++) {
cnt[i]++;
}

LeetCode 686

455 Periodic Strings UVa

11022 String Factoring UVa

11452 Dancing the Cheeky-Cheeky UVa(kmp字符串周期)

12604 Caesar Cipher UVa (kmp查找)

12467 Secret Word UVa

11019 Matrix Matcher UVa (二维匹配问题)

Pattern Find SPOJ(字符口中匹配kmp)

Anthem of Berland codeforces(kmp+自动机+dp)

MUH and Cube Walls codeforces(kmp)

Prefixes and Suffixes codeforces(kmp+前缀统计)

参考资料：

字符串部分简介 - OI Wiki

https://cp-algorithms.com/

https://www-igm.univ-mlv.fr/~lecroq/ 字符串算法

最后

以上就是阳光芒果为你收集整理的前缀函数及kmp算法1、字符串基础2、前缀函数3、应用的全部内容，希望文章能够帮你解决前缀函数及kmp算法1、字符串基础2、前缀函数3、应用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：算法笔记
浏览次数：80 次浏览
发布日期：2023-09-19 21:05:11
本文链接：https://www.kaopuke.com/article/k-p-k_14_uzo_2_f1_12__23__26_5.html

前缀函数及kmp算法1、字符串基础2、前缀函数3、应用

概述

1、字符串基础

1.1 字符集

1.2 字符串

1.3 子串

1.4 子序列

1.5 后缀

1.6 前缀

1.7 字典序

1.8 回文串

2、前缀函数

2.1 朴素算法

2.2 优化算法一

2.3 优化算法二

3、应用

3.1 字符串周期

3.2 字符串查找

3.3 构造自动机

3.4 前缀统计

最后

评论列表共有 0 条评论

发表评论取消回复

前缀函数及kmp算法1、字符串基础2、前缀函数3、应用

概述

1、字符串基础

1.1 字符集

1.2 字符串

1.3 子串

1.4 子序列

1.5 后缀

1.6 前缀

1.7 字典序

1.8 回文串

2、前缀函数

2.1 朴素算法

2.2 优化算法一

2.3 优化算法二

3、应用

3.1 字符串周期

3.2 字符串查找

3.3 构造自动机

3.4 前缀统计

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复