UVa11475 - Extend to Palindrome (KMP algorithm 詳解)

題目大意：

給你一字串，請新增字元讓這字串變成迴文，但新增字元數量要最少。
迴文：從左邊讀與從右邊讀意思都一樣
題目善意提示：這題不要給經驗不足的新手做 ^^

分析

這題是 KMP (Knuth-Morris-Pratt’s) Algorithm 的小變化題，先介紹 KMP algorithm。

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

KMP algorithm 介紹

在線性時間內找出段落(Pattern) 在文字(text) 中哪裡出現過。
對 Pattern 找出次長相同前綴後綴，在使用 DP 將時間複雜度壓縮

QUESTION 1: Pattern and text 是甚麼意思

如果用平常使用者較為了解的方式說明，就像是你在網頁搜尋(使用 ctrl + F) 某個特定文字時，某個特地文字就是 Pattern 而被搜尋的文字則是 text。

QUESTION 2: 此演算法的時間複雜度

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

KMP algorithm 原理

在實現 KMP algorithm 前，必須要先對 Pattern 找出次長相同前綴，通常被稱為 KMP_process()，並透過一陣列紀錄，再根據文字去比對，如果在迴圈當下字元比對不正確時則回到 DP 當下 index 的 Value 去比對，確認現在的值是否為也是 Pattern 中的某部分。

KMP algorithm 實現與說明

由於我認為在程式碼中加上好懂得註解十分好懂，所以我就根據每一行程式碼進行說明，相信會讓讀者更好學會此演算法。
如果對下方說明還是不了解，可以點擊此Abdul Bari 所教導的 KMP algorithm 觀看影片，他會跟你說嗨喔！也許能夠讓你更了解 KMP algorithm 運作，或許是我解釋不好。

KMP 演算法主要由 kmp_process 與 kmp_search 這兩個 function 而成，讀者只要能看懂此兩 function 應該就能夠學會 KMP 的 80%。

kmp_process

string  strB ;
int b[MAXN] ;
// b[] value 表示 strB當下此字元上次前綴的 index，如果已經沒有前綴則設定 -1

void kmp_process(){
    int n = strB.length() ,i = 0 ,  j = -1 ;
    // j = 前綴的長度
    //strB 是 pattern , j = -1 時代表沒有辦法再回推到前一個次長相同前綴
    b[0] = -1 ;
    // 由於 strB[0] 絕對沒有前綴所以設定 -1 
    while(i < n ){ //對從 Pattern 的第 0 個字元到第 i 字元找出次長相同前綴
        while(j >= 0 && strB[i] != strB[j]) j = b[j] ;
        // j >= 0 代表還可以有機會找出 次長相同前綴
        // strB[i] != strB[j] 則代表他們字元不同，於是在這裡把 j 值設為 b[j]
        // 當 j 只要被設定成 -1 就代表完全沒有次長相同前綴
        i++ ; j++ ;
        b[i] = j ;
        // strB[i] 上次前綴的 index 值或是將 j 設定成 0 而不設定成 -1 是因為
        // 他有可能會是 strB[0] 長度只有 1 的前綴
    }

    //debug 供應測試用
    //    for(int k = 0 ; k <= n ; k++)
    //        cout << b[k] << ' ' ;
    //    cout << '\n' ;
}

這樣 kmp_process 就完成了！

kmp

string strA ;
//strA 是 text

void kmp_search(){
    int n = strA.length() , m=strB.length() , i=0 , j=0  ;
    while(i < n ){ //對從 text 找出搜尋哪裡符合 Pattern 
        while(j >= 0 && strA[i] != strB[j]) j = b[j] ;
        // j >= 0  代表還可以有機會是 pattern 的前綴
        // strA[i] != strB[j]  則代表他們字元不同，於是在這裡把 j 改為 b[j]
        // b[j] 說明請看 kmp_process 宣告 b[j] 時的解釋
        i++ ; j++ ;
        if (j == m) { // j 已經跟 pattern 的長度相同了
            printf("P is found at index %d in T\n", i - j); 
            // 告訴使用者在哪裡找出
            j = b[j];
            // 將 j 設定成此字元上次前綴的 index
        }
    }
}

用紙筆去模擬 KMP

有時候用想或用看的可能不太能夠懂這演算法，那就用寫的吧！這裡有兩題，可以幫助你更好搞懂 KMP，如果你願意用紙筆去模擬。

EXERCISE 2 Run kmp_preprocess() on P = ‘ABABA’ and show the b array !
EXERCISE 2 Run kmp_search() with P = ‘ABABA’ and T = ‘ACABAABABDABABA’. Explain how the KMP search looks like?

大衛我自己解這兩題練習的紀錄，不過後來因為有為了要讓自己在更釐清觀念而稍微改一下練習，所以不要認為我的是標準答案，可能只有近似於答案

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

題目是詢問迴文，那跟 KMP algorithm 有甚麼關係呢？這就是為甚麼題目有給一個善意題型的關係了，由於大部分讀者都會誤判這題為水題，所以才給這個提示以免花太多時間把程式碼寫的雜亂又不會 AC。如果將題目給的字串顛倒做為 pattern 則 KMP 最後的 j 就會是原本的字串已經有的迴文長度，我們只需要補足就好了！

是不是沒有一個舉例，會讓人很不好懂呢？那我們就來舉例吧！

SITUATION : 題目字串 xyz :

正常字串 : xyz
顛倒字串 : zyx

他們經過 KMP algorithm 後最後的 j 會是多少？答案是 1，所以我們只要將顛倒字元從 1 開始輸出顛倒字元就會是迴文了！(這裡字串的 index 一開始設定為 0，配合 C++)

正確答案: xyzyx

參考連結：

Competitive Programming 3　(book)
KMP算法詳解

心得

其實我在學習 KMP 的時候覺得我已經學會 Z-algorithm 拉，幹嘛還要在學其他的？但是我發現到如果只有學會其中一種演算法會使自己的思維能力受限，就像是井底之蛙一樣。那樣不好，所以我再花時間學習 KMP，KMP 我學習的時間也沒有很長大約花了 3 小時的時間，我想應該是風平學長介紹的書很好用的關係吧！讓我在學習此演算法時不需要自學，有一本書引導我可以讓我學習的更快！

謝謝風平學長

學習演算法的過程中通常都是無聊的，令人想睡的。大部分的人都認為學習演算法不如去學習網頁，因為學習網頁可以很快地得到回饋，不想演算法只能夠得到題目的「AC」罷了。但我不這麼認為，學習演算法可以讓自己獲得很多思維的想法，他們都可以應用在生活上，我不後悔學習演算法，不如說，我很高興可以學到演算法，可以讓自己在面對很多問題時之前過去的自己在學習演算法而擴展的思維可以幫助到自己，擁有比別人更傑出的想法。

題目程式碼

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

也希望大家想要學習的知識都可以快速學習而成，不要因為自身的環境不足而學習不到。

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 100020
using namespace std;
string strA , strB ;
int b[MAXN] , p[MAXN] ;

void kmp_process(){
    int n = strB.length() ,i = 0 ,  j = -1 ;
    b[0] = -1 ;
    while(i < n ){
        while(j >= 0 && strB[i] != strB[j]) j = b[j] ;
        i++ ; j++ ;
        b[i] = j ;
    }

    //debug
//    for(int k = 0 ; k <= n ; k++)
//        cout << b[k] << ' ' ;
//    cout << '\n' ;
}

int kmp(){
    int n = strA.length() , m=strB.length() , i=0 , j=0  ;
    while(i < n ){
        while(j >= 0 && strA[i] != strB[j]) j = b[j] ;
        i++ ; j++ ;
    }
    return j ;
}


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

    while(cin >> strA){
        strB = strA;
        reverse(strB.begin() , strB.end());
        kmp_process();
        int n = kmp() ;
        cout << strA << strB.substr(n) << '\n' ;
    }
    return 0;
}