前綴函數(shù)

1. 定義

1.1 前綴 & 真前綴

前綴是指從串首開(kāi)始到某個(gè)位置 i 結(jié)束的一個(gè)特殊子串。字符串 S 的以 i 結(jié)尾的前綴表示為 prefix(S,i) = S[0..i]
真前綴指除了 S 本身的 S 的前綴。

1.2 后綴 & 真后綴

后綴是指從某個(gè)位置 i 開(kāi)始到整個(gè)串末尾結(jié)束的一個(gè)特殊子串。字符串 S 的從 i 開(kāi)頭的后綴表示為 suffix(S,i) = S[i..|S|-1]
真后綴指除了 S 本身的 S 的后綴。

1.3 前綴函數(shù)

給定一個(gè)長(zhǎng)度為 n 的字符串 s，其前綴函數(shù)定義為一個(gè)長(zhǎng)度為 n 的數(shù)組 \pi。其中 \pi[i] 含義為：

  • 如果子串 s[0..i] 有相等的真前綴 s[0..k_j-1] 和真后綴 s[i-(k_j-1)..i]，那么 \pi 為最大的相等的真前后綴長(zhǎng)度，即 \pi[i] = max\{ k_j \}
  • 如果子串 s[0..i] 沒(méi)有相等的真前后綴，則 \pi[i] = 0

1.4 字符串的周期

對(duì)于字符串 s 和 0 \lt p \leq |s|，若 s[i] = s[i+p] 對(duì)于所有 i \in [0, |s|-p-1] 成立，則稱(chēng) p 是 s 的周期。

1.5 字符串的 border

對(duì)于字符串 s 和 0 \leq r \lt |s|，若 s 長(zhǎng)度為 r 的前綴和長(zhǎng)度為 r 的后綴相等，就稱(chēng) s 長(zhǎng)度為 r 的前綴（后綴）是 s 的 border 。

【注】易知前綴函數(shù) \pi[i] 對(duì)應(yīng)的就是字符串 s[0..i] 的最長(zhǎng) border 的長(zhǎng)度。

2. 性質(zhì)

  • 如果字符串 s 有長(zhǎng)度為 r 的 border，則 |s| - r 是 s 的周期。

  • 如果字符串 s 的前綴函數(shù)為 \pi，|s| = n，則：

  1. s 所有的 border 長(zhǎng)度為 \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 的最長(zhǎng) border 的長(zhǎng)度，n - \pi[n-1] 是 s 的最小周期。

3. 實(shí)現(xiàn)

根據(jù)前綴函數(shù)的定義我們可以發(fā)現(xiàn)，相鄰的前綴函數(shù)值至多增加 1 ，故可以得到字符串 s 的前綴函數(shù)的計(jì)算公式：

  • 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}

【注】計(jì)算字符串的前綴函數(shù)的思想和 KMP 算法中計(jì)算字符串失配數(shù)組的思想非常相似。

4. 應(yīng)用

4.1 KMP

前綴函數(shù)可以用來(lái)實(shí)現(xiàn) KMP 算法，思路為：拼接模式串 s 和主串 t，得到 S = s + \# + t，\# 為不在 s 和 t 中出現(xiàn)的字符。設(shè) m = |s| \\ n = |t| 計(jì)算拼接后的字符串 S 的前綴函數(shù)，當(dāng)出現(xiàn) i \gt m \wedge \pi[i] = m 時(shí)，說(shuō)明此時(shí)模式串匹配上了主串的子串 t_{i-2m} \cdots t_{i-m-1}。

整個(gè)算法時(shí)間復(fù)雜度為 O(n+m) 。

4.2 字符串周期 & border

根據(jù)上文中給出的性質(zhì)，可以很容易求出字符串 s 的字符串周期 & border。假設(shè) |s| = m，則可以在 O(m) 時(shí)間內(nèi)求出 s 的所有周期 & border。

4.3 統(tǒng)計(jì)每個(gè)前綴出現(xiàn)次數(shù)

  • 統(tǒng)計(jì)字符串 s 的所有前綴子串在 s 中出現(xiàn)的次數(shù)，m = |s|。
  1. 首先統(tǒng)計(jì)前綴數(shù)組值 \pi[i]，\pi[i] 表示字符串 s[0..i] 最長(zhǎng)相等真前后綴長(zhǎng)度，即說(shuō)明前綴 s[0..\pi[i]-1] 在 s[0..i] 中出現(xiàn)了 1 次（不包括前綴本身）。
  2. 前綴數(shù)組值統(tǒng)計(jì)后，只統(tǒng)計(jì)出了每個(gè)前綴作為某個(gè)字符串 s[0..i] 的最長(zhǎng)真后綴的出現(xiàn)次數(shù)，而沒(méi)有統(tǒng)計(jì)非最長(zhǎng)真后綴的出現(xiàn)次數(shù)，故根據(jù) \pi 數(shù)組的性質(zhì)統(tǒng)計(jì)非最長(zhǎng)真后綴的出現(xiàn)次數(shù)。
  3. 加上每個(gè)前綴本身 1 次。
ll ans[MAXN];       // 對(duì)應(yīng)長(zhǎng)度的前綴在字符串中出現(xiàn)的次數(shù) 
void getAns(ll m) {
    // ans[0] 沒(méi)有實(shí)際意義
    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];
}
  • 統(tǒng)計(jì)字符串 s 的所有前綴子串在 t 中出現(xiàn)的次數(shù)，m = |s|, n = |t| 。拼接字符串 s 和 t，使得 S = s + \# + t 。
  1. 首先統(tǒng)計(jì)前綴數(shù)組值 \pi[i](i > m)，\pi[i] 表示字符串 S[0..i] 最長(zhǎng)相等真前后綴長(zhǎng)度，即說(shuō)明前綴 S[0..\pi[i]-1] 在 S[0..i] 中出現(xiàn)了 1 次（不包括前綴本身），易知最長(zhǎng)真前后綴都不會(huì)包含界定符 \#，故統(tǒng)計(jì)得到的只是字符串 t 中的。
  2. 前綴數(shù)組值統(tǒng)計(jì)后，只統(tǒng)計(jì)出了每個(gè)前綴作為某個(gè)字符串 S[0..i] 的最長(zhǎng)真后綴的出現(xiàn)次數(shù)，而沒(méi)有統(tǒng)計(jì)非最長(zhǎng)真后綴的出現(xiàn)次數(shù)，故根據(jù) \pi 數(shù)組的性質(zhì)統(tǒng)計(jì)非最長(zhǎng)真后綴的出現(xiàn)次數(shù)。
ll ans[MAXN];       // 對(duì)應(yīng)長(zhǎng)度的前綴在字符串中出現(xiàn)的次數(shù) 
void getAns(ll m, ll n) {
    // ans[0] 沒(méi)有實(shí)際意義
    // 只統(tǒng)計(jì)字符串 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 不同子串?dāng)?shù)目

給定字符串 s，其長(zhǎng)度 |s| = m，計(jì)算 s 中不同的子串的數(shù)目。

  • 設(shè)字符串 s[0..i] 的不同子串?dāng)?shù)目為 k，則向 s[0..i] 末尾添加一個(gè)字符后得到字符串 s[0..i+1]。顯然 s[0..i+1] 的子串中可能會(huì)出現(xiàn)一些新的以 s[i+1] 結(jié)尾的子串。
  • 反轉(zhuǎn)字符串 s[0..i+1] 得到字符串 t，則問(wèn)題變成統(tǒng)計(jì)以 s[i+1] 開(kāi)頭且未在 t 的其他地方出現(xiàn)的前綴數(shù)目。
  • 設(shè) t 的前綴函數(shù)的最大值為 \pi_{max}，則最長(zhǎng)的出現(xiàn)在 t 其他地方的前綴長(zhǎng)度為 \pi_{max}，故更短的前綴也一定出現(xiàn)了。
  • 因此，字符串 s 新增一個(gè)末尾字符 s[i+1] 后新出現(xiàn)的子串的數(shù)目為 |s| + 1 - \pi_{max}。

【注】從頭部添加、頭部移除或尾部移除后計(jì)算不同子串的思想類(lèi)似。

4.5 字符串壓縮

  • 給定字符串 s，其長(zhǎng)度 |s| = n，我們希望找到一個(gè)最短的字符串 t，使得 s 為 t 的一份或多份拷貝的拼接表示。
  • 顯然，我們只需要找到 t 的長(zhǎng)度即可，該問(wèn)題的答案即為長(zhǎng)度為該值的 s 的前綴。

根據(jù)上文的性質(zhì)可知，如果計(jì)算出 s 的前綴函數(shù)之后，s 的最小周期為 k = n - \pi[n-1]。由字符串的周期的定義可知，最后字符串 s 刪去每段周期長(zhǎng)度的字符串后，剩余的最后一段字符串長(zhǎng)度不一定是 k。故如果 k | n，則 k 即是 t 的長(zhǎng)度，否則不存在一個(gè)有效的壓縮，即 t 的長(zhǎng)度為 n 。

5. 代碼

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

// 前綴函數(shù)
struct PrefixFunction {
    #ifndef _PREFIXFUNCTION_
    #define ll int
    #define MAXN 1000005
    #endif
    ll cnt;             // 字符串的 border（或周期）個(gè)數(shù)
    ll pi[MAXN];        // 前綴函數(shù)
    ll border[MAXN];    // border 長(zhǎng)度數(shù)組（從大到?。?    ll period[MAXN];    // 周期數(shù)組（從小到大）
    PrefixFunction(): cnt(0) {}
    // 計(jì)算前綴函數(shù)
    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];
            }
        }
    }
    // 計(jì)算所有 border 的長(zhǎng)度 
    void getBorder(ll n) {
        ll count = 0;
        ll j = pi[n-1];
        while(j) {
            border[count++] = j;
            j = pi[j-1];
        }
        cnt = count;
    }
    // 計(jì)算所有周期
    void getPeriod(ll n) {
        ll count = 0;
        ll j = pi[n-1];
        while(j) {
            period[count++] = n - j;
            j = pi[j-1];
        }
        cnt = count;
    }
};
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容