# Z-algorithm 理解

> 先來廢話一下，這個演算法其實我在一年前就已經看過了，不知道是看到誰寫的 Z-value 我一直以為跟什麼統計有關，然後就不太趕去碰了XD
> 剛好今天是我在刷 *1700 的題目，看到這題很多人做，然後就把它學起來了><
> 因為我學演算法如果不用常常就會直接忘記，所以我才會特地打這篇記錄一下~

## 定義
先來說說在學這個東西之前需要先搞清楚的東西，主要就兩個而已。
- Z-ary 又稱 Z 陣列，我們稱 Z(i) 為 $Z_i$ (Z 陣列內的第 $i$ 項)
- l,r 目前的計算範圍，這裡先不多做解釋。

### Z 陣列
這裡解釋一下 Z-ary 裡面的東西的意義，建議在讀的時候可以一起模擬一下喔~

$Z[i]$ 代表這樣一個等式成立：$$s[0 \sim z[i]-1]] = s[i \sim i+z[i]-1]$$

舉個例子，例如今天有一個字串 $AABAA$
很明顯，$z[0] = 5$(自己帶一次上面等式就知道了)
再舉一個例子，$z[2] = 0$(因為 s[2]!=s[0])
$z[3] = 2$ 因為 $s[3 \sim 4] = s[0 \sim 1]$

好，介紹完ㄌ，那我們來開始介紹怎麼實作吧!
(至於應用的部分，我最後再說

## 實作

我覺得觀念上有一點點點像是 KMP 或是 DP? 的想法(不會也沒關係。
主要就是後面的值要由前面算好的的轉移過來(幹話

直接放上程式碼，我覺得比較好的學習方式是去看我後面的解釋再回來對應這段程式碼。

for(int i=1,l=1,r=1;i<s.size();i++){
        if(i<=r){
            z[i] = min(z[i-l],r-i+1);
        }
        while(i+z[i]<s.size()&&s[i+z[i]]==s[z[i]])z[i]++;
        if(i+z[i]-1>r){
            l = i;
            r = i+z[i]-1;
        }
    }

先從第一行開始，for 迴圈的宣告，i 從 1 開始的原因是前面說到的，當 $i = 0$ 的時候答案很明顯就是字串長度阿 所以就直接忽略掉，一方面也是避免後面的過程出錯。

接下來直接看到第 5 行，這裡很明顯就是再進行向前推的動作，就是直接暴力往前看。
(其實如果要直接暴力做的話，把2~4行註解掉就是暴力了。

接下來進入重點。

先看 6~9，它的意思就是，如果目前這個位置延伸出去後大於 r 的話，那就更新 $l,r$。這樣你就知道 $l,r$ 是幹嘛的了，就是在說目前已經算過的區間!
那這樣不就直接紀錄 $r$ 就好了嗎，幹嘛還多記一個 $l$。
紀錄 $l$ 的用途在於，如果說目前這個位置 $i$ 在這個區間裡的話，那麼 $s[l \sim i]$ 必定就會等於 $s[0 \sim i-l]$
因為前面保證了一件事情，就是 $l$ 這個位置一定符合 s 的前綴，換句話說也就是 $s[l] = s[0]$。

那了解了上面的觀念後有什麼意義嗎? 那可以知道一件事情，在算到 i 這個位置前，前面一定都算過了。另一個觀念就是，我可以保證$s[i] = s[i-l]$。
那麼，我就可以直接套用前面算到的 z[i] = z[i-l]，但這樣問題其實蠻大的，就是如果 $i+z[i-l]$ 在 $r$ 裡面($i+z[i-l] \leq r$)， 那就可以保證 $$s[i \sim i+z[i-l+1]] = s[0 \sim z[i-l]] = s[i-l \sim i-l+z[i-l]]$$

所以這就是第 3 行在做的事情，為什麼要加上 min 就是為了避免去算到不能保證的地方(也就是沒算過的地方。

那如果超出去了怎麼辦? 那就只能暴力囉!
但是這樣暴力是會均攤的，每次遇到的點都沒走過，所以最後複雜度就會是 $O(n)$

## 應用
如果一個位置 $i$ 的 $i+z[i]==s.size()$
那就代表從這裡就會是前綴 = 後綴的地方。
可以用來這樣找~

裸題的話就直接看這題ㄅ 以下我附程式：

https://codeforces.com/contest/126/problem/B

int z[1000100];
void solve(){
    string s;    
    cin>>s;
    for(int i=1,l=1,r=1;i<s.size();i++){
        if(i<=r){
            z[i] = min(z[i-l],r-i+1);
        }
        while(i+z[i]<s.size()&&s[i+z[i]]==s[z[i]])z[i]++;
        if(i+z[i]-1>r){
            l = i;
            r = i+z[i]-1;
        }
    }

    int ans = 0,bemax = 0;
    for(int i=1;i<s.size();i++){
        if(i+z[i]==s.size()&&z[i]<=bemax){
            cmax(ans,z[i]); //可以一路到end
            //小於bemax的用義是，還需要符合字串'中'最大的那個
        }
        if(z[i]>bemax){
            bemax = z[i]; // 字串中的字最多可以符合的前綴
        }
    }

    if(ans==0){
        cout<<"Just a legend\n";
    }
    else{
        string ss;
        for(int i=0;i<ans;i++)ss+=s[i];
        cout<<ss<<"\n";
    }
}

上面內容有錯都歡迎來跟我說:D