# 字串演算法 — Main–Lorentz

:::spoiler 目錄
[TOC]
:::

:::info
**先備知識與說明：**

- $a+b$ 代表字串 $a$ 和字串 $b$ 的相接
- 所有字串表示都是 0-based
- $s[l \ldots r]$ 代表 $s$ 的第 $l$ 個字元到第 $r$ 個字元形成的子字串
- $\bar{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 \ldots ptr-1] = s[\mid u \mid-k_1 \ldots \mid u \mid - 1]$ 的最大 $k_1$。（下圖粉色箭頭）
- $R$: $s[ptr \ldots ptr+k_2-1] = s[\mid u \mid \ldots \mid u \mid + k_2-1]$ 的最大 $k_2$。（下圖綠色箭頭）

:::warning
但是 $k_1, k_2$ 仍有上界：
$k_1$ 不可大於等於 $l$，否則重串區間就不會包含中就會有某個長度為 $2l$ 的區間不包含 $\mid u \mid$ 的位置。

$k_2$ 不可大於等於 $l$，否則 $s[ptr \ldots \mid u \mid + k_2-1]$ 為重串（以下圖來說，就是指 $c\ a\ b\ a\ b\ c\ a\ b\ a\ b$ 為重串），但這不符合左偏重串的定義。
:::


---

### 4. 快速求得 k1, k2
透過 z-function，我們可以快速的找到 $k_1, k_2$。

:::info
**複習 z-function**

定義一個函式 $Z(s)$，回傳一個長度為 $\mid s \mid$ 的陣列 $z$，其中 $z[i]$ 為 $s[0..n]$ 跟 $s[i..n]$ 的最長共同前綴。

這個可以在 $O(\mid s \mid)$ 的時間複雜度的時間內找到。
:::

- $k_1$: 對 $\bar{u}$ 做 z-function。
- $k_2$: 對 $v + \# + u$（$\#$ 是個不在 $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 討論