Codeforces 126B - Password (Z-algorithm 講解)

題目大意：

給你一字串 X，試問有沒有一個子字串 S，在 X 的頭、尾巴、中間都出現。
，在 X 的 prefix , suffix and Beside prefix and suffix appear。

分析：

這題是 Z algorithm 的模板題，先介紹 Z-algorithm。
此題有多種解，這裡使用 Z-algorithm 解

專門解決在線性時間中在一段文字 (text) 中找到我們所需要的段落 (pattern)
與此類似的演算法: KMP algorithm
由於此題是 Z-algorithm 的模板題，只要能夠了解 Z-algorithm 就能解決此問題。
這題為教學題，但此問題還有一點點的小設計，需要稍加解釋才能完全理解。

Z-algorithm 介紹

Z-algorithm 精隨: 透過 x,y 兩變數與 「Z 陣列」找出此字串中「最長共同前綴總和 (Longest Common Prefix)」

QUESTION 1: x,y and 「Z 陣列」是甚麼?

等下會解釋XD，很快，看不到 1 分鐘就能知道了。

QUESTION 2: 此演算法的複雜度呢?

複雜度 \(O(text + pattern)\)

Z-algorithm 原理

Z Array

在實現 Z-algorithm 需要用到一陣列，「Z Array」。

我們查看字串的長度，並建立一陣列與字串長度相當，其就是 Z Array，Z 陣列中的 i 表示當前「最長共同前綴總和 (Longest Common Prefix)」

\(Z[0]\) 毫無幫助XD，由於 Z[0] 只有自己他沒辦法達到共同，他們都是自己，即為都是「同一個字串」，因而無意義。

x and y

在實現 Z-algorithm 還需要用到兩變數 \( x , y\)。

x = 目前共同前綴的第一個字元
y = 目前共同前綴的最後一字元在字串中的 index

Z-algorithm 再除了此題目以外的應用

通常是應用在尋找段落 (pattern)，將文本字串 (text) 與段落連接起來，視段落為「P」、文字為「T」，並加上一個沒有在 P and T 出現過的字元，假設為「\$」，產生出「P\$T」，最後產生 Z array，如果 Z array 中的某個值等於 P 的長度，則段落出現在此處。

因為從未出現過的字元使得「最長共同前綴總和 (Longest Common Prefix)」最大只能到 P，從未出現的字元阻斷了增加的可能性，才能應用在此。

Z-algorithm 實現與說明

由於我認為在程式碼中加上好懂得註解十分好懂，所以我就根據每一行程式碼進行說明，相信會讓讀者更好學會此演算法。
如果對下方說明還是不了解，可以點擊此連結觀看動畫，也許能夠讓你更了解 Z-algorithm 運作。

string s ;
int z[s.length()] = {} ;

for(int i = 1 ; i < s.length() ; i++ ){ 
    z[i] = max(0,min(z[i-x] , y - i + 1));
    // z[i-x] 直接詢問 z[i-x] 共同前綴嘗是多少，
    // 如果當前是在目前的共同前綴中，那理所當然現在的 i 必會等於最初的共同前綴 i-x 值，
    // 如果不是，那必定會是 0。
    // y-i+1  此共同前綴理應只會有 y-i+1 個
    //如果 z[i-x] 比較小，代表沒有從 i 位置開始的前綴字串，否則 z[i-x] 應該要更大，所以
    //也就表示 z[i] == z[k]。
    // 如果 y-i+1 比較小，代表這次的共同前綴比較小，因為 z[i-x] 更大，也就代表應該有從這
    //裡開始的共同前綴
    while(i + z[i] < s.length() && s[z[i]] == s[i+z[i]] ){
        x = i ;
        y = i + z[i] ;
        z[i]++ ;
        //進行比對，查看 s[z[i]] 的位置是否等於 s[i+z[i]] 的位置是的話就比對下一個
    }
}

這樣 Z-algorithm 就完成了！

焦點回到題目上，解開題目的小設計

我們可以透過 Z-algorithm 找到「最長共同前綴總和 (Longest Common Prefix)」，但題目的要求字串後面也需要前綴呀，有可能共同最長前綴是 abcabcabc，但是這樣會是 6 呀，應該要是 abc、長度 3，才行的！

於是我們需要加一個 if 來找出 3，來防止我們的程式出現瑕疵，這裡用程式碼來解釋會更好解釋，逆向思考有時候會比普通的思考方式來的更好。我們一樣根據每一行程式碼進行說明。

for(int i = 0 ; i < s.length() ; i++)
    if(z[i] == s.length() - i && maxn >= s.length()-i ){
    // z[i] == s.length() - i -> 如果 z[i] 等於字串剩下的長度那保證會有
    //後綴，通常 i 都會接近 s.length() 時才會符合
    // maxn >= s.length()-i -> 再從 0 to s.length() 時勢必會找到並經過
    //「最長共同前綴總和 (Longest Common Prefix)」，只要他比後綴還要長或相等 
    //(還需要先滿足第一個條件，才能判斷到此條件)，就肯定代表中間已經也有經
    //過「最長共同前綴總和 (Longest Common Prefix)」，尾巴這個並不會是第一次經過，
    //如果尾巴是那就代表他只有兩次的共同前綴。
        cout << s.substr(0,z[i]); // 輸出答案
        return 0 ;
    }
    maxn = max(maxn , z[i]);
    //經過時更新 「最長共同前綴總和 (Longest Common Prefix)」
}

參考連結

Algorithm - Z 演算法
Z Algorithm
Z Algorithm_codeforces
Codeforces 126B Password（Z算法）

心得

老實講，這題學習很快www，廢話，程式碼很少呀，但撰寫文章倒是花了很多時間，補了許多學習時沒有注意到的漏洞。此演算法寫起來十分簡單，但它裡面蘊藏著許多小細節，我花了很多時間去整理。沒想到快要跟學「點分治」的時間快要一樣久了，看來我的學習能力還挺不好，還需要多加強了 QAQ

不過也要感謝網路上已經有許多優秀的人放了教學文章在上面可以讓我學習與思考，要是沒有他們我應該也沒辦法順利推出來這些想法，還是習慣用紙筆去理解一次演算法，雖然很花時間，但印象深刻。RAM 太少常常忘記自己迴圈是做到第幾次，然後就一直鬼打牆

不過也對自己表示一點小失望，學習能力有點偏差呀！好希望自己的頭腦可以再清楚一點，能夠可以讀懂優秀大神寫的演算法，而不是每次都要花上 5,6 個小時來理解，在撞牆期中常常會覺得自己很沒用呀。

那怕是一點點的進步也好，都可以給在學習路上的我很大的自信。

雖然每次在學習演算法總是會讓我覺得難過，因為是自學很容易遇到學習障礙，但我認為這是我應該要學會的基礎。我並不是幸運的孩子，我勢必要先做出一些成果，讓資源跟大神可以關注到我，在提拔我或幫助我成長。在還沒有大神們關注到我之前，我會默默耕耘，繼續努力的！

為了讓讀者與未來的我看到之前的我學習是怎麼學習的，我就在這邊放入我為了學習這份演算法而在紙上實作的紀錄吧！

題目程式碼

其實就是沒有附上說明的程式碼，我也花了三個小時撰寫文章，看得懂跟說得出來真的是兩回事，也許還有人覺得我說的很差，不過我已經盡力解釋拉。希望可以幫助到各位。

於是這裡就補述一些題目給的資料範圍限制與標頭檔了

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 1000020
using namespace std;
int z[MAXN] = {} ;
int x=0 , y=0 , maxn = 0;
string s ;


int main()
{
#ifdef LOCAL
    freopen("in1.txt","r",stdin);
#endif // LOCAL

    cin >> s ;
    for(int i = 1 ; i < s.length() ; i++ ){
        z[i] = max(0,min(z[i-x] , y - i + 1));
        while(i + z[i] < s.length() && s[z[i]] == s[i+z[i]] ){
            x = i ;
            y = i + z[i] ;
            z[i]++ ;
        }
    }

    for(int i = 0 ; i < s.length() ; i++)
        if(z[i] == s.length() - i && maxn >= s.length()-i ){
            cout << s.substr(0,z[i]);
            return 0 ;
        }
        maxn = max(maxn , z[i]);
    }
    cout << "Just a legend" ;
    return 0;
}