String_Matching

String Basic
Original
- 方法
- 程式碼
Hashing
Rabin-Karp rolling hash function
- 比對：rolling
KMP
Z Algorithm

String Basic

string ：有排序的字元集合

substring：一段連續的字串子集合

subsequence：依斷按順序但可不連續的字串子集合

suffix：從後面開始一樣的子字串

prefix：從前面開始一樣的子字串

ex:

String = abcdefg

Substring = “abcd”, “efg”… (連續)

Subsequence = “acdf”, “dfg”…. (不連續)

suffix = “efg”, “defg”….

prefix = “abcd”, “ab”…

Original

方法

兩字串A,B，找出所有B出現在A中的位置，

很直覺的不斷從頭比對，若有字母不符合，則整體再往後退一個，繼續從頭比對

程式碼

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

簡單的字串比對，時間複雜度為O(|A|)，| |表示字串的長度。

過程請見以下：

A = “abcdefg”
B = “cde”

alt text

worst case

有可能造成時間複雜度成長為O(|A||B|)

過程請見以下：

A = “aaaaa….aaa”
B = “aaaaa….aab”

alt text

Hashing

就是幫字串分類到有限數字裡

函數f：string -> {0,1,2….}

要求：

1.函數f容易取得

字串分佈均勻，意即碰撞次數愈小愈好

思考：

f(A) ≠ f(B) ，可以推得 A ≠ B
f(A) = f(B) ，可以推得 A = B or A ≠ B (發生碰撞)
若分n類,碰撞機率為1/n

Rabin-Karp rolling hash function

類似p進位制，分成q類(mod q，即對q取餘數)

p,q取不同的質數可讓字串分佈的更加均勻

比對：rolling

以拿A,B兩字串比較為例

1.先計算A所有prefix的hash value,時間複雜度為 O(|A|)

2.可以得出任何子字串的hash value

3.枚舉A長度為 |B| 的子字串,比較hash value,時間複雜度為O(n)

ex:

A = “abcdefg”

B = “cde”

KMP

Knuth-Morris-Pratt algorithm

使用時機：給定A,B兩字串，尋找B字串是否存在A當中

當B的字串內容，本身有重複的字串時，可用KMP以減少重複否配的時間

ex:

B : aabaab

B字串本身重複 “aab”

方法：先用fail function找出字串B重複的字串

Fail Function

目的：當否配失敗時，能知道字串B要對齊哪裡繼續否配

變數：

B [ ] … 存放字串B

pi [ ] … 紀錄前一個重複字串出現的位置

cur_pos … 目前字串重複的位置

初始化：

程式碼：

void fail(string B, int *pi)
{
        int len = strlen(B);
        pi[0] = -1;
        for( int i = 1, cur_pos = -1; i<len; ++i)
        {
                while(cur_pos >= 0 && B[i] != B[cur_pos+1])
                        cur_pos = pi[cur_pos];
                if(B[i] == B[cur_pos+1])  ++cur_pos;
                pi[i] = cur_pos;
        }
}

Matching

Fail function: 找出各後綴與前綴一樣的最大值

如果後綴 = 前綴 → 可直接位移

String Matching process

Matching 與 Fail function 的作法類似，差別只在於比較的對象不同

程式碼：

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

Fail function + Matching • Complexity – 關鍵: while-loop – cur_pos 每次只會 +1 或往前 – 均攤後 𝒪( A + B )