前缀函数与KMP

· · 个人记录

前缀函数与KMP

前缀函数

定义

前缀函数数π的定义为：

1.如果子串s[0,...i]有一对真后缀与真前 缀：s[0,...k-1]和s[i-(k-1)...i]那么π[i]就是这个相等的真前缀的长度

2.如果不止有一对相等，则π[i]即最长的那一对

3.如果没有相等，那么π[i]等于0

    例如：
    对于字符串abcabcd有：
    π[0]=0 无真后缀与真前缀
    π[1]=0 无相等的真前缀与真后缀
    π[2]=0 无相等的真前缀与真后缀
    π[3]=1 相等的真前缀与真后缀为a
    π[4]=2 相等的真前缀与真后缀为ab
    π[5]=3 相等的真前缀与真后缀为abc
    π[6]=0 无相等的真前缀与真后缀

算法与优化

优化1：

相邻的前缀函数值至多增加1，

移动到下一个位置时，前缀函数的值要么增加一，要么维持不变，要么减少

优化2：

如果我们找到了长度j,只需要比较a[i+1]和s[j]如果他们相等，那么就有π[i+1]=j+1

否则需要找到子串s[0,...j]的长度仅次于j的第二长度，使得前缀性质得到保存

优化后的完整代码

void function(string a)
{
    int len=(int)a.length();

    for(int i=1;i<len;i++)
    {
        int j=pi[i-1];

        while(j>0 && a[i]!=a[j])
            j=pi[j-1];

        if(a[i]==a[j])
            j++;

        pi[i]=j;
    }

    return;
}

KMP

典型问题

给定一个文本t和一个字符串s，尝试找到并展示s在t中的所有出现

分析

用n表示字符串s的长度 用m表示文本t的长度

构造一个字符串s+"#"+t（“#”指代既不在s中出现又不在t中出现的字符）

计算该字符的前缀函数 根据定义如果有π[i]=n出现 说明s完整出现在该位置

位置的计算：i-(n-1)-(n+1)=i-2*n

时间复杂度：O(n+m） 空间复杂度：O(n)

字符串的周期

定义

周期： 对于字符串s和0<p<=|s|,若s[i]对于所有的i属于[0,|s|-p-1]成立，称p是s的周期

border： 对于字符串s和0<=r<|s|,若有s长度为r的前缀与后缀相等，称s长度为r的前缀是s的border

计算

|s|-r是s的周期

所有border的长度： π[n-1]，π[π[n-1]]...

最小周期： n-π[n-1]

统计前缀出现次数

第一类问题

给定一个长度为n的字符串s，统计每个前缀s[0,...i]在同一字符串的出现次数

solution

首先让我们来解决第一个问题。考虑位置i 的前缀函数值π[i] 。根据定义，其意味着字符串s一个长度为 π[i] 的前缀在位置i出现并以i为右端点，同时不存在一个更长的前缀满足前述定义。与此同时，更短的前缀可能以该位置为右端点。容易看出，我们遇到了在计算前缀函数时已经回答过的问题：给定一个长度为j的前缀，同时其也是一个右端点位于i的后缀，下一个更小的前缀长度k<j 是多少？该长度的前缀需同时也是一个右端点为i的后缀。因此以位置i为右端点，有长度为π[π[i]-1]的前缀，有长度为π[π[π[i]-1]-1]的前缀，有长度为0的前缀，等等，直到长度变为 。故而我们可以通过下述方式计算答案。

vector<int> ans(n + 1);
for (int i = 0; i < n; i++) ans[pi[i]]++;
for (int i = n - 1; i > 0; i--) ans[pi[i - 1]] += ans[i];
for (int i = 0; i <= n; i++) ans[i]++;

第二类问题

统计每个前缀s[0,...i]在另一个给定字符串t中的出现次数。

solution

我们应用来自 Knuth-Morris-Pratt 的技巧：构造一个字符串s+"#"+t并计算其前缀函数。与第一个问题唯一的不同之处在于，我们只关心与字符串t相关的前缀函数值，即t>=n+1的π[i]。有了这些值之后，我们可以同样应用在第一个问题中的算法来解决该问题。