字串處理

Who am I ?

下降資工所一年級

什麼是字串?

"Hi你好"

"ATCGATCGGGGGG"

"asdff;lkjsadflkj"

正式的定義

給定字元集 $\Sigma$ ，長度為 $n$ 的字串 $A$，

$A = a_0 a_1 \dots a_{n-1}$

一些名詞定義

給訂一字串 $A = a_0 a_1 \dots a_{n-1}$

子字串

$A[i,j] = a_{i} a_{i+1} \dots a_{j}$
子序列

$B = a_{q_1} a_{q_2} \dots a_{q_m}$

$0 \le q_1 < q_2 < \dots q_m < n$

一些名詞定義

前綴 (Prefix)

$P_A(i) = A[0,i]$
後綴 (Suffix)

$S_A(i) = A[i,n-1]$

例子

舉例來說，如果$A = \texttt{abcbbab}$，那 $\texttt{bcb}$ 是他的子字串， $\texttt{acb}$ 是他的子序列，而 $\texttt{bbab}$ 是他的一個後綴。

字串的儲存

Trie

通常最基本的儲存方式就是用一個陣列依序將字串的每一個字元存下來。

不過當我們要同時儲存許多字串時，可能就要花點巧思了。而這邊要介紹一個可以同時儲存多個字串的資料結構 ─ 字典樹或Trie。

Trie (cont.)

Trie的道理非常簡單，其實就是用一棵樹來儲存字串。

在這棵樹上，每個點上(除了根節點之外)都有一個字元，而從根節點一路走到某個節點，依序經過的字元串起來就是那個點代表的字串。

最後我們再記錄哪些點是一個字串的最後一個字元即可！

如下圖就是一個儲存$\{A_1 = \texttt{abc}, A_2 =\texttt{abde}, A_3 = \texttt{bc}, A_4 = \texttt{bcd}\}$的trie

給定一個字典樹Trie $T = \{V, E\}$，我們定義$P_T(v)$為從根節點走到$v$所得出的字串。

而Trie的基本操作也都很簡單，如要新增一個字串$A$，我們就從根節點開始，依照字串$A$的第$0, 1, 2, \cdots, n-1$個字元，如果此字元在當前節點的子節點中就繼續走下去，否則就新增一個節點。

字串匹配

在處理字串問題時，會很常處理字串匹配問題。

請問這篇文章中出現多少次歐巴馬？
請問這段 DNA 序列中出現多少次 AAA ？
很常在文件使用的 ctrl+f 搜尋

正式一點來說，字串匹配是個這樣的問題

給你兩個字串 $A$, $B$，找出所有 $B$ 出現在 $A$ 中的位置。

簡單的做法

for (int st = 0; st + lenB <= lenA; st++) {
    int mat = 0;
    while (mat < lenB && A[st + mat] == B[mat]) mat++;
    if (mat == lenB) output(st);
}

這份 code 有兩的部分，一個是枚舉 $B$ 可能出現的位置，

接著是一個 while 從這個位置判斷 $B$ 跟 $A$ 是否一樣。

這邊也可以使用 strcmp(A+st,B) == 0。

這樣寫好不好呢？

其實可以證明這樣的期望複雜度是 $O(|A|)$。

可惜的是，最差的情況可以到$O(|A||B|)$！

更糟的是很容易構造出例子。

如$A = \texttt{AAAAA} \dots \texttt{AA}, B = \texttt{AAA} \dots \texttt{B}$，

這樣雖然$B$從來沒有出現在$A$中，

但是每個位置我們都必需匹配到 $B$ 的最後一個字元才能確定匹配失敗！

說是這樣說，如果題目生測資太過於隨機的話，

其實好好寫個樸素的解法很容易過 OAO，

生測資很困難啊QA Q。

怎樣加速呢？

讓我們再看一次這份 code。

for (int st = 0; st + lenB <= lenA; st++) {
    int mat = 0;
    while (mat < lenB && A[st + mat] == B[mat]) mat++;
    if (mat == lenB) output(st);
}

如果可以讓 while 的部分變成接近 $O(1)$，

我們就可以加速到 $O(|A|)$ 判斷兩個字串的長度。

Hashing

基本想法

想辦法幫一個字串算出它的「特徵」，

就像你在找東西前會先觀察它的顏色、大小等等，利用這個快速判斷他在不在視線範圍之內，說穿了就是定義一種分類方式。

Hash 就是個這樣的做法，利用分類加速你的搜尋速度。

Hash 函數

找到一個分類函數，即是一個$f: \mathbb{S}(\Sigma) \mapsto \mathbb{Z}$，把所有可能的字串打到有界的整數，不妨說$f(s) \in [0, M-1] \; \forall s$吧！
這個函數最好是均勻分部在$[0, M-1]$上。
計算這個函數最好不需花太多時間！
一個滿足以上條件的函數我們就稱作「好的」 Hash function

之後呢?

有了Hash function後有什麼用呢？

雖然我們無法保證$A \neq B \; \Rightarrow f(A) \neq f(B)$，

因為$f$把有無窮多個元素的字串集合打到有限個整數上，

當然會有許多字串被打到同一個整數！

但至少我們會知道

$f(A) \neq f(B) \quad \Rightarrow \quad A \neq B$

也就是說如果兩個字串的Hash value不一樣，那我們連匹配都不需要了，他們鐵定不相等！

至於Hash function要怎麼找呢？

Rabin-Karp rolling hash function

這是個常用的方法，給定$p, q$ 跟長度為 $n$ 字串 $A$，令

$f(A) = a_0 p^{n-1} + a_1 p^{n-2} + \cdots + a_{n-2} p + a_{n-1} \mod{q}$

$=\sum_{0}^{n-1} a_i p^{n-i-1} \mod{q}$

看起來很複雜，其實就是字串$A$在$p$進位制代表的值模$q$而已！

那這個函數有符合我們的需求嗎？
首先他把每個字串打到$[0, q-1]$，

可以想成他把所有字串分成$q$類。
另外數學家跟我們說，如果$p,q$取兩個不同的質數，通常結果會不錯，非常均勻！

Sliding Window

另外計算這個函數只需要$O(|A|)$，並且他還有一些很好的性質！

遞迴性

$f(A) \equiv f(A[0, n-2]) \times p + a_{n-1} \pmod{q}$
子字串的 hash value 與前綴的關係

$f(A[i, j]) \equiv f(A[0, j]) - p^{j-i+1} f(A[0, i-1]) \pmod{q}$

所以對於一個字串 $A$，可以先利用遞迴性在 $O(|A|)$ 的時間內算出所有前綴的hash，$f(P_A(i))$。

對於任何一個子字串$A[i,j]$，我們可以利用前綴預處理完的 hash 值 $O(1)$算出結果。

簡單的寫個 code，

typedef long long LL;
char a[N]; LL hsa[N];
int p,q;
LL mul(LL a, LL b, int mod){return a*b%mod;}
LL add(LL a, LL b, int mod){return (a+b)%mod;}
void init(string a){
    pw[0] = 1;
    for(int i=1; i<N; i++)
        pw[i] = mul(pw[i-1], q);

    for(int i=0; i<(int)a.length(); i++)
        hsa[i] = add((i==0?0:hsa[i-1])*p, (int)a[i]);
}
int hsf(int l,int r){
    return hsa[r] - ((l==0)?0:mul(hsa[l-1], pw[r-l+1],q));
}

這樣我們就有任意子字串的 hash value 可以用了。

回到我們字串匹配的問題，我們只需要事先算出 $A$ 所有前綴的hash value和$f(B)$，
再枚舉$A$所有長度為$|B|$的子字串(差不多$O(A)$個，
最後計算這些子字串的 hash value 是不是等於$f(B)$，總共只需要$O(N)$。

會不會壞掉呢？

等等！回想我們剛剛說的：我們知道$f(A) \neq f(B) \Rightarrow A \neq B$，

但卻無法保證$f(A) = f(B) \Rightarrow A = B$啊？

有人可能會想說：「相等時重新檢查一次」，
但如果$A = \texttt{AAA} \dots \texttt{AAA}, B = \texttt{AA} \dots \texttt{AA}$，就又會又退化成$O(|A||B|)$了！

那怎麼辦呢？
答案是：把$q$取大一點，然後就相信 $f(A) = f(B)$的機率很小，不會發生！

事實上如果$f$是均勻的，那$f(A) = k$的機率差不多是$1/q$！

只要$q$取夠大，比如一個 long long 的質數，差不多$10^{15}$，那麼兩個不同的字串碰撞的機率是$10^{-15}$，

是一個人被閃電打到兩次的機率(一次機率差不多是$8 \times 10^{-7}$)，不太可能啦！

如果碰撞了？

有些常用的質數有人會故意構造會碰撞的測資

像是大家很愛用的 $10^9+7$ 或是 $10^9+9$，
或是真的很衰就是被雷打到了，不管怎樣反正就是你因為碰撞WA了。

要怎辦呢？

這時候可以嘗試使用兩組不同的 $(p_1, q_1), (p_2, q_2)$ 湊出的兩個hash function $f_1(x), f_2(x)$，並使用數對 $(H_1 = f_1(S),H_2 = f_2(S))$ 當作你的hash value，

也就是

$f_1(A) \neq f_1(B) \quad or \quad f_2(A) \neq f_2(B) \Rightarrow A \neq B$

這樣碰撞的機率就會大大減少，再WA...你有其他bug機率可能還比較高(?)。

KMP

想法

當我們在做最普通的匹配時...

定義

對於一個字串$B = b_0 b_1 \cdots b_{m-1}$，我們定義

$F_B(i) = \max \{ k: P_B(k) = B[0, k] = B[i-k, i] \}$

$\quad\quad\quad \quad \text{if } i \neq 0 \text{ and at least a $k$ exists}$
$\quad \quad= -1$, else
$F(i)+1$也稱作在第$i$個位置的共同前後綴長度

例子

舉個長一點的例子，如果$S = \texttt{ababaabababaababa}$，那麼$F_{S}(j)$會是：

由上面的推論,我們總結 $F(j)$ 的一個非常重要的性質:

$F_B(j)$ 告訴我們在拿 $B$ 去匹配 $A$ 的過程中，如果 $B[0, j]$ 已經匹配成功，

但在第 $j + 1$ 個位置匹配失敗了，應該要把 $B$ 的第 $F(j)$ 個字元對齊原本 $B[j]$ 的位置繼續匹配!

再舉個例子,容易知道如果 $B = \texttt{aabaabd}$,則 $F(j) = \{−1, 0, −1, 0, 1, 2, −1\}$。

假設我們已經匹配 $B[0, 4]$，但在第 5 個字元出問題了，

    01234567
A = aabaaa?????
    |||||*        Matching failed at position 5
B = aabaabd         
       ||*        F(4) = 1, Matching failed at position 2
       aabaabd
        |*        F(1) = 0
        aabaabd

這樣我們一次可能往前一大步，而不用每次位移一格重新匹配了!
F 可以說是個快速重新對齊的的function ！

怎樣計算 F 呢？

假設我們已經求出了 $F(i),\forall 0 \le i \le n$，現在要求 $F(n + 1)$，

根據定義相當於要求最大的 $k = k′ + 1$ 使 $B[0,k] = B[n+1−k,n+1]$。
而$B[0,k] = B[n+1−k,n+1]$

$\Leftrightarrow B[0,k′] = B[n−k′,n]∧B[k′ +1] = B[n+1]$

由失敗函數的定義我們知道 $k′$ 最大只能是 $F(n)$，如果此時 $B[F(n) + 1] = B[n + 1]$，我們立刻便知道 $F(n + 1) = F(n) + 1$。

但如果不是怎麼辦? 難道必需 $k′ = F(n) − 1,F(n) − 2··· ,0$ 一直試下去嗎?不要忘記我們已經算出所有 $j \le n$ 的 $F(j)$ 了,

我們便把當前位置 $n$ 對齊 B[F(F(n))]。

也就是下一個要試的 k′ 是 $F(F(n))$！

如果又失敗,我們便再試 $F^{3}(n),F^4(n), \cdots$，

直到終於成功或是確認沒有 $k$ 存在 ($F(n + 1) = −1$)。

計算 F 的 code

void build_fail_function(string B, int *fail) {
    int len = B.length(), current_pos;
    current_pos = fail[0] = -1; //Specially fail[0] = -1
    for( int i = 1 ; i < len ; i ++ ) {
        while( current_pos != -1
               && B[current_pos + 1] != B[i] ) {
            current_pos = fail[current_pos];
        }
        if( B[ current_pos + 1 ] == B[i] ) current_pos ++;
        fail[i] = current_pos;
    }
}

匹配的 code

void match(string A, string B, int *fail) {
    int lenA = A.length(), lenB = B.length();
    int current_pos = -1;
    for( int i = 0 ; i < lenA ; i ++ ) {
        while( current_pos != -1 
               && B[current_pos + 1] != A[i] ) {
            current_pos = fail[current_pos];
        }
        if( B[current_pos + 1] == A[i] ) current_pos ++;
        if( current_pos == lenB - 1 ) {
            // Match !
            // A[i - lenB + 1, i] = B
            current_pos = fail[current_pos];
        }
    }
}

$B[0, F(i)]$是$B$最長的一個前綴使得$B[0, F(i)] = B[i - F(i), i]$，但 $F(i) \neq i$

令$F^k(i) = \overbrace{f \circ f \circ \cdots \circ f}^{k} (i)$，則：

$\exists n, \; F^n(i) = -1$

$F^{k+1}(i) < F^{k}(i) \quad \text{if} \quad F^k(i) \neq -1$

令$K = \{ i, F(i), F^2(i) , \cdots , F^{n-1}(i), F^n(i) = -1\}$，

則 $B[0, k] = B[i-k, i] \; \Leftrightarrow \; k \in K$

$-1 \leq F(i+1) \leq F(i) + 1$

最後我們分析一下KMP的時間複雜度，參考範例程式碼，可以發現不管在計算 $F$ 或是在匹配，對於每一次的匹配，

當前$B$的匹配位置(current_pos)會

(a).被疊代入 $F$ 若干次。
(b).如果匹配成功，便加$1$。
但我們知道每次疊代current_pos至少會減$1$，並且疊代到$-1$時便會停止，

因此(a)中疊代的次數不會超過(b)被執行的次數！
而(b)又不會超過字串的長度，

所以KMP的時間複雜度是$O(|A| + |B|)$，線性！

Z-value

在計算一個答案時，如果能妥善利用已知的資訊，便可以加速計算所需的時間。

而Z Algorithm ( Z-value ) 便是充分的利用這一點。

現在我們就來介紹這個名字很帥氣的演算法。

算法內容

Z function 的核心概念在建出一個 $Z$ 陣列， $Z[i]$ 代表從第 $i$ 個字元開始所形成的後綴與原字串的共同最長前綴有多長，唯一的例外是 $Z[0]$ 通常強制被設成 $0$ 。

首先我們定義Z function

對於一個字串$A = a_0 a_1 \cdots a_{n-1}$，定義

$Z_A(i) = 0, \quad \text{if } i = 0 \text{ or } A[i] \neq A[0]$

$\max \{ k : A[0, k-1] = A[i, i+k-1] \},\text{else}$

看起來和失敗函數$F(i)$有點像，

但不一樣的是$Z(i)$表示$A$的後綴$S_A(i)$，

也就是從$A[i]$開始的字串，可以和$A$自已匹配多長。

看個例子

舉例而言，對於字串$S = \texttt{"ababaabababaababa"}$來說，Z function的值為：

現在我們需要一個快速求出所有 $Z(i)$ 的方法，假設我們已經知道了 $Z(i) = z$，也就是 $A[0, z-1] = A[i, i+z-1]$。

那麼 $Z(i+1), Z(i+2), \cdots , Z(i+z-1)$ 是否會和 $Z(1), Z(2), \cdots, Z(z-1)$ 有關係呢？

事實上Z function有一個很重要的性質是對於一個字串$A = a_0 a_1 \cdots a_{n-1}$，如果$Z(i) = z$，則

$A[k] = A[i+k], \quad \text{if } \; 0 \leq k < z$.
$A[z] \neq A[i+z]$.
令$L = i, R = i + z - 1$，現在假設$L \leq j \leq R, j' = j - L$，則：
- 如果 $j' + Z(j') < z$，則 $Z(j) = Z(j')$
- 如果 $j' + Z(j') > z$，則 $Z(j) = R - j + 1$
- 如果 $j' + Z(j') = z$，則 $Z(j) \geq R - j + 1 = Z(j')$

Case 1

如果 $j' + Z(j') < z$，則 $Z(j) = Z(j')$

Case 2

如果 $j' + Z(j') > z$，則 $Z(j) = R - j + 1$

Case 3

如果 $j' + Z(j') = z$，則 $Z(j) \geq R - j + 1 = Z(j')$

最後一種情況雖然我們無法直接得出 $Z(j)$，但我們至少會知道$Z(j) ≥ Z(j′)$，

因此我們繼續從 R 下去匹配就可以了!

讓我們來看看 code

char A[MXN]; int Z[MXN];
Z[0] = 0;
int L = 0, R = 0;
for ( int i = 1 ; i < len ; i ++ ) {
    if ( i > R ) Z[i] = 0;
    else {
        int ip = i - L;
        if ( ip + Z[ip] < Z[L] ) Z[i] = Z[ip]; // Case 1
        else Z[i] = R - i + 1; // Case 2, 3
    }
    while ( i + Z[i] < len && A[ i + Z[i] ] == A[ Z[i] ] ) Z[i] ++;
    if ( i + Z[i] - 1 > R ) {
        L = i;
        R = i + Z[i] - 1;
    }
}

不過這和字串匹配有什麼關係呢？假設我們要拿 $B$ 匹配 $A$ ，只要令 $C = B \phi A$，其中 $\phi$ 是從來沒有在 $A, B$ 間出現過的字元，

這樣如果 $A[i, i+k-1] = B, \: k = |B|$ ，必有 $C[k+i+1, 2k+i] = C[0, k-1]$ ，也就是 $Z_C(k+i+1) = k$。

那些 kmp z-value 教我的事

來想些題目吧，

給你一個字串 $S$, 要你找出一個最短的字串 $K$, 使得 $K$ 重複若干次接在一起後會變成 $S$. 輸出 matching 到的長度。

這題有兩派作法， KMP 或 Z-value 皆可。

以 Z-value 而言

做完 $Z$ 之後我們只要看看那些 $|S|$ 因數位置的 $Z$ 值就知道答案了。
以 KMP 而言

我們只要做完 predo 其實就知道答案了。令 $K = |S| - dp[|S|-1]$ ，如果 $K$ 是 $|S|$ 的因數，那麼 $S[0\,..\,K-1]$ 就是答案，若否則 $S$ 自己就是答案。

KMP

ABABABAB
P----P..
..S----S

ans: 2

AAABAA
PP....
....SS

ans: -1

其他方法

其實這題如果使用 hash 可以做到很快，先找出所有 $n$ 的因數，從小到大每個因數 $d$，判斷所以 $hash(A[i \times d,(i+1 \times d -1)])$ 是否相同，如果是就輸出答案，這樣可以做到 ${\Sigma}_{d|n} d$，數量量級是 $O(n)$ 的。

來想些題目吧 (cont.)

給你一個字串 $S$, 求一個最短的字串 $T$, 使得你可以用若干個 $T$ 疊成 $S$. (重疊之處必須相同) 給個提示，我能用 Z-value 作到 $O(n)$，而用 KMP 作到 $O(n)$ 。

AC 自動機

What this is?

就是...傳上去你就會AC了(?)
不...那是自動 AC 機。
我第一次看到覺得名字很帥就是了。

他的全名是 Aho-Corasick Algorithm

內容簡介

可以說是 KMP 的強化板。

如果今天我們要在字串$A$上搜尋很多字串 $B_1, B_2, \cdots B_n$要怎麼做？

當然我們可以做 $n$ 次KMP得到一個$O(n|A| + \sum|B| )$的方法，
但信不信由你，其實我們可以在 $O(|A| + \sum |B| )$ 的時間完成

做法簡介

先用 $B_1, B_2, \cdots B_n$ 建出一顆 trie
對於 trie上的每個節點 $v$，建一個類似kmp 的 failure function 的 failure link，

$f(v)$ 是指到樹上的另外一個點，

並且把所有 $B_i$ 的節點標記起來。

用a, c, ab, cc,cca, bab, caa 建出的 AC 自動機，藍線是 failure link。

要尋找 $B_i$ 在 $A$ 上匹配的時候每次就會在 trie 上走，每次 $A[i]$ 會嘗試匹配，

如果失敗就會往回走到 $f(v)$ 繼續嘗試匹配，

如果走到標記的點就幫 $B_i$ 的 count++

看看 code ?

root->fail = NULL;
queue<Node*> que;
que.push_back(root);
while ( !que.empty() ) {
    Node *fa = que.front(); que.pop_front();
    for (auto it = fa->child.begin(); it != fa->child.end(); it++) {
        Node *cur = it->second, *ptr = fa->fail;
        while ( ptr && !ptr->child.count(it->first) ) ptr = ptr->fail;
        cur->fail = ptr ? ptr->child[it->first] : root;
        que.push(cur);
    }
}

演算法其他詳細內容或用法，請見進階字串的章節。

字串處理 – Who am I ? – 什麼是字串?

b92paul

字串處理 – Who am I ? – 什麼是字串?

0 0 (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/platform.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();

ioi-camp-2016-string-basic-slide

字串處理

Who am I ?

什麼是字串?

正式的定義

一些名詞定義

一些名詞定義

例子

字串的儲存

Trie

Trie (cont.)

字串匹配

簡單的做法

怎樣加速呢？

Hashing

基本想法

Hash 函數

之後呢?

Rabin-Karp rolling hash function

Sliding Window

會不會壞掉呢？

如果碰撞了？

KMP

想法

定義

例子

怎樣計算 F 呢？

計算 F 的 code

匹配的 code

Z-value

Z-value

算法內容

看個例子

Case 1

Case 2

Case 3

讓我們來看看 code

那些 kmp z-value 教我的事

來想些題目吧，

KMP

其他方法

來想些題目吧 (cont.)

AC 自動機

What this is?

內容簡介

做法簡介

看看 code ?

0 0