# 字串演算法

## Rolling Hash 演算法
- [Leetcode 214 Shortest Palindrome](https://leetcode.com/problems/shortest-palindrome/)
- 時間複雜度為 $O(n)$
- `s="bcd"`
- 正著算：2->23->234
- 倒著算：2->32->432

long long ll = 0, rr = 0, base = 1;
for(int i=0;i<n;i++){
    int dif = s[i] - 'a';
    ll = (ll * 26 + dif) % mod;
    rr = (rr + base * dif) % mod;
    base = (base * 26) % mod;
}

## KMP 演算法
- [Leetcode 28 Strstr()](https://leetcode.com/problems/implement-strstr/)
- 比對 `t` 是否為 `s` 的子字串
- 其中 $|s|=m$ ，$|t|=n$
- 計算 `t` 的 failure function 時間複雜度為 $O(n)$
- 比對的時間複雜度為 $O(m)$

    // failure function: 對每個 prefix，找出次長相同前綴後綴長度
    //    AAAB -> 0 1 2 0
    //   AAABA -> 0 1 2 0 1
    // ABABCAB -> 0 0 1 2 0 1 2
    vector<int> getNext(string t){
        int n = t.length();
        vector<int> next(n, 0);
        
        for(int i=1, len=0; i<n;i++){
            while(len && t[i]!=t[len]) len = next[len-1];
            if(t[i]==t[len])    len++;
            next[i] = len;
        }
        return next;
    }
    int strStr(string s, string t) {
        int m = s.length(), n = t.length();
        vector<int> next = getNext(t);
        
        for(int i=0, len=0; i<m;i++){
            while(len && s[i]!=t[len]) len = next[len-1];
            if(s[i]==t[len])    len++;
            if(len==n)  return i-len+1;
        }
        return -1;
    }

## Suffix Array 演算法
- (1) 倍增演算法建構 suffix array 和 rank: `s = "banana"`
- 長度 1: `rank = "102020"`
- 長度 2: `rank = "213130"`
- 長度 4: `rank = "325140"` <-> `sa = "531042"`

int sa[1005], rk[1005], tmp[1005], lcpa[1005];

void build_SA(string s){
    int n = s.length(), gap = max(n,128);

    for(int i = 0; i < n; i++)    rk[i] = s[i]-'a';
    for(int wide = 1; ; wide <<= 1){    // 執行 O(logn) 輪
        set<int> s;
        unordered_map<int,int> mp;
        int idx = 0;

        for(int i = 0; i < n; i++){
            if(i + wide < n)    s.insert(rk[i] * gap + rk[i+wide]);
            else                s.insert(rk[i] * gap);
        }
        for(auto data:s)        mp[data] = idx++;
        for(int i = 0; i < n; i++){
            if(i + wide < n)    rk[i] = mp[rk[i] * gap + rk[i+wide]];
            else                rk[i] = mp[rk[i] * gap];
        }
        if(idx == n)            break;
    }
    for(int i = 0; i < n; i++)    sa[rk[i]] = i;
}

-
- 把倍增法的排序改成 `counting sort` 可降低時間複雜度為 $O(nlogn)$
- 另外還有 $O(n)$ 時間複雜度的演算法 e.g. SAIS / DC3
- (2) 建構 LCP 陣列
- `LCPA[i]` : 排名第 i 名和第 i-1 名的後綴，最長共同前綴長度
- 起始位置分別為 sa[i] 和 sa[i-1]
- 從最長的後綴開始，逐次去掉開頭字元，跳著填寫 LCP Array
- 最長後綴：排名為 rk[0]，比較 sa[rk[0]] 和 sa[rk[0]-1]
- 次長後綴：排名為 rk[1]，比較 sa[rk[1]] 和 sa[rk[1]-1]
- ...
- `由上一格結果 -1 後，繼續往下比對`

void build_lcp_array(string s){
    int n = s.length(), lcp = 0;
    for(int i = 0; i < n; i++){ // 從最長後綴開始填
        if(rk[i]==0){ lcpa[0] = 0; continue;}
        
        int ii = sa[rk[i]];  // ii = i
        int jj = sa[rk[i]-1];
        if(lcp > 0)   lcp -= 1;
        while(s[ii+lcp] == s[jj+lcp])   lcp++;
        lcpa[rk[i]] = lcp;
    }
}