前缀函数

1. 定义

1.1 前缀 & 真前缀

前缀是指从串首开始到某个位置 i 结束的一个特殊子串。字符串 S 的以 i 结尾的前缀表示为 prefix(S,i) = S[0..i]
真前缀指除了 S 本身的 S 的前缀。

1.2 后缀 & 真后缀

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

1.3 前缀函数

给定一个长度为 n 的字符串 s,其前缀函数定义为一个长度为 n 的数组 \pi。其中 \pi[i] 含义为:

  • 如果子串 s[0..i] 有相等的真前缀 s[0..k_j-1] 和真后缀 s[i-(k_j-1)..i],那么 \pi 为最大的相等的真前后缀长度,即 \pi[i] = max\{ k_j \}
  • 如果子串 s[0..i] 没有相等的真前后缀,则 \pi[i] = 0

1.4 字符串的周期

对于字符串 s0 \lt p \leq |s|,若 s[i] = s[i+p] 对于所有 i \in [0, |s|-p-1] 成立,则称 ps周期

1.5 字符串的 border

对于字符串 s0 \leq r \lt |s|,若 s 长度为 r 的前缀和长度为 r 的后缀相等,就称 s 长度为 r 的前缀(后缀)是 sborder

【注】易知前缀函数 \pi[i] 对应的就是字符串 s[0..i] 的最长 border 的长度。

2. 性质

  • 如果字符串 s 有长度为 r 的 border,则 |s| - rs 的周期。

  • 如果字符串 s 的前缀函数为 \pi|s| = n,则:

  1. s 所有的 border 长度为 \pi[n-1],\pi[\pi[n-1]-1],\cdots
  2. s 所有的周期为 n-\pi[n-1],n-\pi[\pi[n-1]-1],\cdots
  3. \pi[n-1]s 的最长 border 的长度,n - \pi[n-1]s 的最小周期。

3. 实现

根据前缀函数的定义我们可以发现,相邻的前缀函数值至多增加 1 ,故可以得到字符串 s 的前缀函数的计算公式:

  • s[0] = 0
  • 如果 s[i] = s[\pi[i-1]],则 \pi[i] = \pi[i-1] + 1
  • 如果 s[i] \ne s[\pi[i-1]],令 j = \pi[i-1]。若 s[i] \ne s[j],则令 j = \pi[j-1],直到 j = 0 \vee s[i] = s[j] 为止,则 \pi[i] = \begin{cases} 0 & if \ s[i] \ne s[j] \\ j + 1 & if \ s[i] = s[j] \end{cases}

【注】计算字符串的前缀函数的思想和 KMP 算法中计算字符串失配数组的思想非常相似。

4. 应用

4.1 KMP

前缀函数可以用来实现 KMP 算法,思路为:拼接模式串 s 和主串 t,得到 S = s + \# + t\# 为不在 st 中出现的字符。设 m = |s| \\ n = |t| 计算拼接后的字符串 S 的前缀函数,当出现 i \gt m \wedge \pi[i] = m 时,说明此时模式串匹配上了主串的子串 t_{i-2m} \cdots t_{i-m-1}

整个算法时间复杂度为 O(n+m)

4.2 字符串周期 & border

根据上文中给出的性质,可以很容易求出字符串 s 的字符串周期 & border。假设 |s| = m,则可以在 O(m) 时间内求出 s 的所有周期 & border。

4.3 统计每个前缀出现次数

  • 统计字符串 s 的所有前缀子串在 s 中出现的次数,m = |s|
  1. 首先统计前缀数组值 \pi[i]\pi[i] 表示字符串 s[0..i] 最长相等真前后缀长度,即说明前缀 s[0..\pi[i]-1]s[0..i] 中出现了 1 次(不包括前缀本身)。
  2. 前缀数组值统计后,只统计出了每个前缀作为某个字符串 s[0..i] 的最长真后缀的出现次数,而没有统计非最长真后缀的出现次数,故根据 \pi 数组的性质统计非最长真后缀的出现次数。
  3. 加上每个前缀本身 1 次。
ll ans[MAXN];       // 对应长度的前缀在字符串中出现的次数 
void getAns(ll m) {
    // ans[0] 没有实际意义
    for(ll i = 0; i < m; ++i)   ++ans[pi[i]];
    for(ll i = m-1; i; --i)     ans[pi[i-1]] += ans[i];
    for(ll i = 0; i <= m; ++i)  ++ans[i];
}
  • 统计字符串 s 的所有前缀子串在 t 中出现的次数,m = |s|, n = |t| 。拼接字符串 st,使得 S = s + \# + t
  1. 首先统计前缀数组值 \pi[i](i > m)\pi[i] 表示字符串 S[0..i] 最长相等真前后缀长度,即说明前缀 S[0..\pi[i]-1]S[0..i] 中出现了 1 次(不包括前缀本身),易知最长真前后缀都不会包含界定符 \#,故统计得到的只是字符串 t 中的。
  2. 前缀数组值统计后,只统计出了每个前缀作为某个字符串 S[0..i] 的最长真后缀的出现次数,而没有统计非最长真后缀的出现次数,故根据 \pi 数组的性质统计非最长真后缀的出现次数。
ll ans[MAXN];       // 对应长度的前缀在字符串中出现的次数 
void getAns(ll m, ll n) {
    // ans[0] 没有实际意义
    // 只统计字符串 t 中的
    for(ll i = m+1; i < n+m+1; ++i)   ++ans[pi[i]];
    for(ll i = m; i; --i)     ans[pi[i-1]] += ans[i];
}

4.4 不同子串数目

给定字符串 s,其长度 |s| = m,计算 s 中不同的子串的数目。

  • 设字符串 s[0..i] 的不同子串数目为 k,则向 s[0..i] 末尾添加一个字符后得到字符串 s[0..i+1]。显然 s[0..i+1] 的子串中可能会出现一些新的以 s[i+1] 结尾的子串。
  • 反转字符串 s[0..i+1] 得到字符串 t,则问题变成统计以 s[i+1] 开头且未在 t 的其他地方出现的前缀数目。
  • t 的前缀函数的最大值为 \pi_{max},则最长的出现在 t 其他地方的前缀长度为 \pi_{max},故更短的前缀也一定出现了。
  • 因此,字符串 s 新增一个末尾字符 s[i+1] 后新出现的子串的数目为 |s| + 1 - \pi_{max}

【注】从头部添加、头部移除或尾部移除后计算不同子串的思想类似。

4.5 字符串压缩

  • 给定字符串 s,其长度 |s| = n,我们希望找到一个最短的字符串 t,使得 st 的一份或多份拷贝的拼接表示。
  • 显然,我们只需要找到 t 的长度即可,该问题的答案即为长度为该值的 s 的前缀。

根据上文的性质可知,如果计算出 s 的前缀函数之后,s 的最小周期为 k = n - \pi[n-1]。由字符串的周期的定义可知,最后字符串 s 删去每段周期长度的字符串后,剩余的最后一段字符串长度不一定是 k。故如果 k | n,则 k 即是 t 的长度,否则不存在一个有效的压缩,即 t 的长度为 n

5. 代码

#include <bits/stdc++.h>
using namespace std;

// 前缀函数
struct PrefixFunction {
    #ifndef _PREFIXFUNCTION_
    #define ll int
    #define MAXN 1000005
    #endif
    ll cnt;             // 字符串的 border(或周期)个数
    ll pi[MAXN];        // 前缀函数
    ll border[MAXN];    // border 长度数组(从大到小)
    ll period[MAXN];    // 周期数组(从小到大)
    PrefixFunction(): cnt(0) {}
    // 计算前缀函数
    void getPi(char *str, ll n) {
        pi[0] = 0;
        ll i = 1, j = pi[i-1];
        while(i < n) {
            if(str[i] == str[j]) {
                pi[i++] = j++ + 1;
            } else if(!j) {
                pi[i++] = j;
            } else {
                j = pi[j-1];
            }
        }
    }
    // 计算所有 border 的长度 
    void getBorder(ll n) {
        ll count = 0;
        ll j = pi[n-1];
        while(j) {
            border[count++] = j;
            j = pi[j-1];
        }
        cnt = count;
    }
    // 计算所有周期
    void getPeriod(ll n) {
        ll count = 0;
        ll j = pi[n-1];
        while(j) {
            period[count++] = n - j;
            j = pi[j-1];
        }
        cnt = count;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,504评论 6 496
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,434评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,089评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,378评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,472评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,506评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,519评论 3 413
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,292评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,738评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,022评论 2 329
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,194评论 1 342
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,873评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,536评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,162评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,413评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,075评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,080评论 2 352