字串演算法 — Main–Lorentz

目錄

• 字串演算法 — Main–Lorentz
  • 目標
  • 演算法
    • 0. 主要想法
    • 1. 定義：左、右中間字元
    • 2. 定義：左偏、右偏重串
    • 3. 對於固定的 ptr，尋找所有重串
    • 4. 快速求得 k1, k2
    • 5. 找到「真正」所有跨越 u, v 的重串
  • 程式碼
  • 範例題目
  • 其他有趣的小討論
  • 參考資料

先備知識與說明：

• $a+b$ 代表字串
  $a$ 和字串
  $b$ 的相接
• 所有字串表示都是 0-based
• $s[l\dots r]$ 代表
  $s$ 的第
  $l$ 個字元到第
  $r$ 個字元形成的子字串
• $\overline{s}$ 代表將
  $s$ 反轉

目標

我們定義

$x$ 是某個任意長度的字串，則

$x+x$ 就被稱作重串，而

$x$ 被稱作原串。

透過一種演算法對於長度為

$n$ 的字串

$s$，在

$O(n\log n)$ 的時間複雜度內，找到最長的重串、重串的數量。

演算法

0. 主要想法

演算法是透過「分治」完成的。

定義變數：

• $s$: 原本的字串
• $u$:
  $s$ 的前一半
• $v$:
  $s$ 的後一半

可以假設已經計算完完全在

$u$ 裡面跟完全在

$v$ 裡面的重串，則剩下的步驟就是要找到跨越

$u$ 跟

$v$ 的重串。

---

1. 定義：左、右中間字元

我們定義「左、右中間字元」分別是

$u$ 的最後一個字元（

$s[\mid u\mid -1]$），

$v$ 的第一個字元（

$[\mid u\mid ]$），因為橫跨

$u$ 跟

$v$ 的重串必定會選到這兩個中間字元，因此在演算法中是必要的。

先看右中間字元，假設有某個橫跨

$u$ 跟

$v$ 的重串，則

$u$ 裡面必定有個位置會對應到右中間字元（指兩個字元都在原串的同個位置），我們將它的位置設為

$ptr$。根據

$ptr$ 的定義，可知道這種重串的長度

$l$ 必定為

$\mid u\mid -ptr$。

在上圖中可以發現右中間字元是可以找到對應的重串的，但左中間字元不行，這是因為對應的字元可能出現在同一側或是不同側，因此我們才需要兩邊的中間字元去尋找重串。

---

2. 定義：左偏、右偏重串

我們定義「基準字元」為某重串

$a+b,a=b$ 中，

$b$ 的第一個字元。

若基準字元在

$u$ 裡面，則該重串被定義為「左偏」，否則為「右偏」。

以下的步驟會演示如何找到左偏重串，右偏重串則類似。

---

3. 對於固定的 ptr，尋找所有重串

雖然我們已經固定了

$ptr$，也能找到對應的

$l$，但這不代表我們找到了重串，因為

$ptr$ 跟右中間字元仍可能出現在不同的重串內。

透過上圖我們可以發現，固定

$ptr$ 後，可以找到一個區間使得所有長度為

$2l$ 的子區間都是重串（如上圖

$[0,10]$ 這個區間內選一個長度為

$10$ 的子字串都是重串），們稱這個區間叫做「重串區間」。

我們將重串區間由兩個變數

$k_1,k_2$ 表示，

$[ptr-k_1,\mid u\mid +k_2-1]$。根據上圖的範例，比較有觀察力的讀者應該可以猜得出來

$k_1,k_2$ 的條件：

• $L$:
  $s[ptr-k_1\dots ptr-1]=s[\mid u\mid -k_1\dots \mid u\mid -1]$ 的最大
  $k_1$。（下圖粉色箭頭）
• $R$:
  $s[ptr\dots ptr+k_2-1]=s[\mid u\mid \dots \mid u\mid +k_2-1]$ 的最大
  $k_2$。（下圖綠色箭頭）

但是

$k_1,k_2$ 仍有上界：

$k_1$ 不可大於等於

$l$，否則重串區間就不會包含中就會有某個長度為

$2l$ 的區間不包含

$\mid u\mid$ 的位置。

$k_2$ 不可大於等於

$l$，否則

$s[ptr\dots \mid u\mid +k_2-1]$ 為重串（以下圖來說，就是指

$cababcabab$ 為重串），但這不符合左偏重串的定義。

---

4. 快速求得 k1, k2

透過 z-function，我們可以快速的找到

$k_1,k_2$。

複習 z-function

定義一個函式

$Z(s)$，回傳一個長度為

$\mid s\mid$ 的陣列

$z$，其中

$z[i]$ 為

$s[0..n]$ 跟

$s[i..n]$ 的最長共同前綴。

這個可以在

$O(\mid s\mid )$ 的時間複雜度的時間內找到。

• $k_1$: 對
  $\overline{u}$ 做 z-function。
• $k_2$: 對
  $v+\mathrm{\#}+u$（
  $\mathrm{\#}$ 是個不在
  $s$ 的字元）做 z-function。

---

5. 找到「真正」所有跨越 u, v 的重串

5-1. 枚舉所有中間字元

上述內容都是針對同一個

$ptr$，實際上的實作中，我們會枚舉

$u$ 的每個字元，有找到和中間字元相同就設為

$ptr$ 尋找

$[L,R]$。

5-2. 以不同方向當作基準

別忘了我們剛剛僅有用到右中間字元找左偏重串，還要用左中間字元找到右偏重串才算找完所有跨越

$u,v$ 的重串。

程式碼

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

LL n, longest = 0;
string s;

vector<LL> z_function(string s){
    vector<LL> ret;
    ret.resize(s.size());
    LL ll = 0, rr = 0; // 可以使用已知資訊區間的 [ll, rr)

    for (LL i=1 ; i<s.size() ; i++){ // 目前要找的索引值
        LL j = 0; // i 需要枚舉前綴的開頭
		
		// 如果 i 還在只知資訊區間就可以先用前面得到的資訊
		// 找 i-ll 的答案，rr-i 是上界
        if (i<rr) j = min(ret[i-ll], rr-i);
        while (s[j]==s[i+j]) j++; // 枚舉已知資訊後的內容
        ret[i] = j;
		
        if (i+j>rr){ // 如果新的範圍大於已知資訊的區間，就更新
            ll = i;
            rr = i+j;
        }
    }

    ret[0] = s.size();
    return ret;
}

LL z_value(vector<LL> &v, LL p){
    if (0<=p && p<v.size()) return v[p];
    return 0;
}

// 尋找字串 s 中的重串數量
LL repetition(string s){

    // 終止條件
    if (s.size()==1){
        return 0;
    }

    // 找到左邊右邊的重串
    LL mid = s.size()/2;
    string u = s.substr(0, mid);
    string v = s.substr(mid);
    string ru(u.rbegin(), u.rend());
    string rv(v.rbegin(), v.rend());
    LL lc = repetition(u);
    LL rc = repetition(v);

    // 尋找中間的重串
    LL total = 0;
    vector<LL> z1 = z_function(ru);
    vector<LL> z2 = z_function(v+'#'+u);
    vector<LL> z3 = z_function(ru+'#'+rv);
    vector<LL> z4 = z_function(v);

    // 找到左偏重串
    for (LL ptr=0 ; ptr<u.size() ; ptr++){
        if (u[ptr]==v[0]){
            LL l = u.size()-ptr;
            LL L = z_value(z1, u.size()-ptr);
            L = min(L, l-1); // 限制長度，不能和 ptr 重疊
            LL R = z_value(z2, v.size()+1+ptr);
            R = min(R, l-1); // 限制長度，確保是左偏重串

            int add = max(0LL, R+L-l+1);
            total += add;
            if (add){
                longest = max(longest, l);
            }
        }
    }

    // 找到右偏重串
    for (LL ptr=0 ; ptr<v.size() ; ptr++){
        if (u.back()==v[ptr]){
            LL l = ptr+1;
            LL L = z_value(z3, u.size()+v.size()-ptr);
            LL R = z_value(z4, ptr+1);
            R = min(R, l-1); // 限制長度，不能和 ptr 重疊

            int add = max(0LL, R+L-l+1);
            total += add;
            if (add){
                longest = max(longest, l);
            }
        }
    }

    return lc+rc+total;
}

int main(){

    // input
    cin >> n;
    cin >> s;

    // process
    int res = repetition(s);
    cout << longest*2 << " " << res << "\n";

    return 0;
}

範例題目

https://codeforces.com/contestInvitation/4d09eace2246e7893a7ac48d8238483daebc4daa

自己生的題目，有問題再告訴我 :>

其他有趣的小討論

1. 在下面的參考資料中可以看到一些關於重串的性質：
   
   我尚未找到資料說明如何構造壓縮，如果有人知道的話可以告訴我。

參考資料

• https://oi-wiki.org/string/main-lorentz/
• https://cp-algorithms.com/string/main_lorentz.html
• 跟 dreamoon 討論