32.字符串匹配

研究問(wèn)題：

在文本T中找到某個(gè)模式P所出現(xiàn)的位置氮惯。
定義文本是一個(gè)長(zhǎng)為 n 的數(shù)組T[0..n-1]，而模式P是一個(gè)長(zhǎng)為 m 的數(shù)組P[0..m- 1],m≤n
并且若T[s..s+(m-1)]=P[0..(m-1)]則稱(chēng)模式P在T中出現(xiàn)且偏移為 s (P在文本T中的位置是從第 s+1 個(gè)開(kāi)始的)

常見(jiàn)算法的時(shí)間：

算法	預(yù)處理時(shí)間	匹配時(shí)間
樸素算法	0	O((n-m+1)m)
Rabin-Karp	$\Theta$ (m)	O((n-m+1)m)
有限自動(dòng)機(jī)算法	O(m\| $\Sigma$ \|)	$\Theta$ (n)
Knuth-Morris-Pratt	$\Theta$ (m)	$\Theta$ (n)

樸素算法

對(duì) n-m+1 個(gè)可能的 s 值做檢測(cè)，看是否滿足T[s..s+(m-1)]=P[0..(m-1)]

實(shí)現(xiàn)代碼：

int naiveStringMatcher(string T, string P){
    int n = T.length();
    int m = P.length();
    for (int s = 0; s < n - m; s++){
        int i;
        for (i = 0; i < m; i++){
            if (T[s + i] != P[i])
            break;
        }
        if (i == m) return s; //返回下標(biāo)s
    }
    return -1; //這里找不到合適的值就返回-1
}

最壞情況下鱼喉，運(yùn)行時(shí)間為 O((n-m+1)m) 如果 m=floor(n/2.) 則運(yùn)行時(shí)間為 $\Theta(n^2)$

Rabin-Karp 算法

Rabin-Karp 算法的預(yù)處理時(shí)間是 $\Theta$ (m)豆巨，最壞情況下運(yùn)行時(shí)間是O((n-m+1)m）蝗罗，但是平均運(yùn)行時(shí)間比較快。

對(duì)于每個(gè)字符串过吻，可以用長(zhǎng)度為 k 的十進(jìn)制數(shù)來(lái)表示由 k 個(gè)連續(xù)的字符組成的字符串，例如字符串31415可以對(duì)應(yīng)十進(jìn)制數(shù)31415杰刽。給定一個(gè)模式 P[0..(m-1)]菠发，假設(shè) p 表示其十進(jìn)制值，對(duì)應(yīng)的文本 T[0..(n-1)]中贺嫂，假設(shè) $t_s$ 表示長(zhǎng)度為 m 的子字符串 T[s..(s+m-1)] 的十進(jìn)制值滓鸠，當(dāng)且僅當(dāng) P[0..(m-1)]=T[s..(s+m-1)] 時(shí)，有 p= $t_s$ 第喳。如果能在時(shí)間 $\Theta$ (m) 內(nèi)計(jì)算出 p 值哥力，并在總時(shí)間 O(n-m+1) 內(nèi)計(jì)算出所有 $t_s$ 值，那么通過(guò)比較所 p 和所有 $t_s$ 值就可以在 $\Theta$ (n) 時(shí)間內(nèi)計(jì)算出所有偏移 s 墩弯。

p 可以運(yùn)用霍納法則在 $\Theta$ (m) 時(shí)間內(nèi)計(jì)算得到：
$p = P[m]+10(P[m-1]+10(P[m-2]+...+10(P[2]+10P[1])))$

$t_s$ 可以迭代得到，因?yàn)椋?br> $t_{s+1} = 10(t_s-10^{m-1}T[s+1])+T[s+m+1]$
每次去掉高位數(shù)字寞射，然后乘以10渔工，再加上低位數(shù)字。

到目前為止的問(wèn)題是 p 和 $t_s$ 的值可能過(guò)大桥温，因此可以選取一個(gè)合適的模 q 來(lái)計(jì)算 p 和 $t_s$ 的模引矩，我們可以在 $\Theta$ (m) 時(shí)間內(nèi)計(jì)算出模 q 的 p 值，并且可以在 $\Theta$ (n-m+1) 時(shí)間內(nèi)計(jì)算出模 q 的所有 $t_s$ 值侵浸。

遞推式：

$t_{s+1} = (d(t_s-T[s+1]h)+T[s+m+1])\ mod\ q$
d為字母表{0, 1, ..., d-1}的進(jìn)制旺韭， $t_s \equiv d^{m-1}\ (mod\ q)$ 是一個(gè)具有 m 數(shù)位的文本窗口的高位數(shù)位上的數(shù)字“1”的值。

但是掏觉， $t_s \equiv p\ (mod\ q)$ 并不能說(shuō)明 $t_s = p$ 区端，反之若 $t_s \neq p\ (mod\ q)$ ，則一定有 $t_s \neq p$ 澳腹。求余的結(jié)果可以用于快速檢測(cè)無(wú)效偏移 s织盼，但是對(duì)于有效偏移，還需要重新對(duì)該偏移逐個(gè)檢測(cè)酱塔，否則就是一個(gè)偽命中點(diǎn)沥邻。

實(shí)現(xiàn)代碼：

int mod(int a, int b){ //求余運(yùn)算
    return (a % b >= 0) ? (a % b) : (a % b + b);
}

void RabinKarpMatcher(string T, string P, int d, int q){
    int n = T.length();
    int m = P.length();
    int h = int(pow(d, m - 1)) % q;
    int p = 0;
    vector<int> t(n - m + 1, 0);
    for (int i = 0; i < m; i++){   // processing 
        p = mod((d * p + P[i]), q);
        t[0] = mod((d * t[0] + T[i]), q);
    }
    for (int s = 0; s <= n - m; s++){  // matching
        if (p == t[s]){
            if (P == T.substr(s, m))
                cout << "s: " << s << endl;
            else
                cout << "error match!" << endl;
        }
        if (s < n - m)
            t[s + 1] = mod((d * (t[s] - T[s] * h) + T[s + m]), q);
    }
}

如果模 q=11，那么當(dāng) Rabin-Karp 算法在文本 T = 3141592653589793 中尋找模式 P = 26 時(shí)羊娃，會(huì)遇到 3 個(gè)偽命中點(diǎn)唐全。即 RabinKarpMatcher(T, P, 10, 11) 時(shí)，會(huì)遇到3個(gè) error match蕊玷！

有限自動(dòng)機(jī)算法

有限自動(dòng)機(jī)是一個(gè)處理信息的簡(jiǎn)單機(jī)器邮利，通過(guò)對(duì)文本字符串 T 進(jìn)行掃描弥雹，找出模式 P 的所有出現(xiàn)位置。這些字符串匹配的自動(dòng)機(jī)只對(duì)文本字符檢查一次近弟，并且檢查每個(gè)字符的時(shí)間為常數(shù)缅糟，因此模式預(yù)處理和建立自動(dòng)機(jī)的時(shí)間為 $\Theta(n)$ 。但是如果字符集 $\Sigma$ 很大的話祷愉，建立自動(dòng)機(jī)的時(shí)間也較多窗宦。

有限自動(dòng)機(jī)的定義：

一個(gè)有限自動(dòng)機(jī)是5個(gè)類(lèi)型的元組： $(Q,\ q_0,\ A,\ \Sigma,\ \delta)$
$Q$ 是狀態(tài)的有限集合
$q_0\in Q$ 是初始狀態(tài)
$A\subseteq Q$ 是一個(gè)特殊的接受狀態(tài)集合
$\Sigma$ 是有限輸入字母表
$\delta$ 是一個(gè)從 $Q \times \Sigma$ 到 $Q$ 的函數(shù)，稱(chēng)為M的轉(zhuǎn)移函數(shù)

為了便于說(shuō)明給定模式 P[0...(m-1)] 的字符串匹配自動(dòng)機(jī)二鳄，定義一個(gè)輔助函數(shù) $\sigma$ 赴涵，稱(chēng)為對(duì)應(yīng) P 的后綴函數(shù)。其中 $\sigma(x)$ 是 $x$ 的后綴 P 的最長(zhǎng)前綴的長(zhǎng)度订讼。
$\sigma(x) = max\{k:\ P_k\sqsupset x\}$
對(duì)于模式 P=ab髓窜，有 $\sigma(\varepsilon)=0$ ， $\sigma(ccaca)=1$ , $\sigma(ccab)=2$ 欺殿。
給定模式 P[0..(m-1)]寄纵，相應(yīng)的字符串匹配自動(dòng)機(jī)定義如下：
1)狀態(tài)集合Q為{0, 1, ..., m}。開(kāi)始狀態(tài) $q_0$ 是0狀態(tài)脖苏，并且只有狀態(tài)m是唯一被接受的狀態(tài)程拭。
2)對(duì)任意的狀態(tài)q和字符a，轉(zhuǎn)移函數(shù) $\delta$ 定義如下：
$\delta(q,a)=\sigma(P_qa)$

一個(gè)自動(dòng)機(jī)的例子：

輸入模式 P = ababaca棍潘，長(zhǎng)度為7個(gè)字符恃鞋，因此有狀態(tài)0, 1, ..., 7，假設(shè)字母表為{a, b, c}
則有:
$\delta(0,a)=\sigma(P_0a)=\sigma(a)=1$
$\delta(0,b)=\sigma(P_0b)=\sigma(b)=0$
$\delta(0,c)=\sigma(P_0c)=\sigma(c)=0$
$\delta(1,a)=\sigma(P_1a)=\sigma(aa)=1$
$\delta(1,b)=\sigma(P_1a)=\sigma(ab)=2$
$\delta(1,c)=\sigma(P_1a)=\sigma(ac)=0$
...
$\delta(6,a)=\sigma(P_6a)=\sigma(ababaca)=7$

因此可以有如下字符串匹配的狀態(tài)轉(zhuǎn)換圖：

狀態(tài)	a	b	c
0	1	0	0
1	1	2	0
2	3	0	0
3	1	4	0
4	5	0	0
5	1	4	6
6	7	0	0
7	1	2	0

其中狀態(tài)7是僅有的接受狀態(tài)

實(shí)現(xiàn)代碼：

vector<vector<int>> computeTransFunc(string P, int len){  //預(yù)處理亦歉，計(jì)算delta
    int m = P.size();
    vector<int> temp(len, 0);
    vector<vector<int>> delta(m + 1, temp);
    for (int q = 0; q <= m; q++){
        int k;
        for (int a = 0; a < len; a++){  // 遍歷字母表恤浪，這里是數(shù)字0到(len-1),如果是小寫(xiě)字母，可以通過(guò)-'a'操作得到對(duì)應(yīng)的0到25
            string Pqa = P.substr(0, q) + to_string(a);
            k = (m + 1 <= q + 2) ? (m + 1) : (q + 2);
            string Pqasub = Pqa;  
            //這里借助一個(gè)Paqsub來(lái)存儲(chǔ)Pqa串的長(zhǎng)度為k的后綴肴楷，因?yàn)閗可能大于Pqa.size()水由，直接調(diào)用Pqa.substr(Pqa.size()-k)會(huì)報(bào)錯(cuò)
            do {
                k--;
                int lenPqa = Pqa.size() - k;
                Pqasub = (lenPqa >= 0) ? Pqa.substr(lenPqa) : Pqa;
            } while (P.substr(0, k) != Pqasub);  // k--直到P的k前綴是Pqa的后綴為止，循環(huán)必然會(huì)停止赛蔫，因?yàn)榭沾侨魏巫址暮缶Y
            delta[q][a] = k;
        }
    }
    return delta;
}
void finiteAutomationMatcher(string T, vector<vector<int>> delta, int m){  //匹配過(guò)程
    //m是唯一接受狀態(tài)绷杜，例如上面例子中的7
    int n = T.size();
    int q = 0;
    for (int i = 0; i < n; i++){
        q = delta[q][T[i] - '0'];
        if (q == m)
            cout << "Pattern occurs with shift" << i + 1 - m << endl;
    }
}
int main(){
    string T("0201010102010");
    string P("0101020");
    vector<vector<int>> delta = computeTransFunc(P, 3);
    finiteAutomationMatcher(T, delta, 7);
    return 1;
}

本算法需要O(m| $\Sigma$ |)的預(yù)處理時(shí)間以及 $\Theta$ (n)的匹配時(shí)間。

Knuth-Morris-Pratt算法

本算法無(wú)需計(jì)算 $\delta$ 濒募，匹配時(shí)間也同樣是 $\Theta$ (n)鞭盟，只需要用到一個(gè)輔助函數(shù) $\pi$ ，它在 $\Theta$ (m)時(shí)間內(nèi)根據(jù)模式預(yù)先計(jì)算出來(lái)瑰剃，并存儲(chǔ)在數(shù)組 $\pi[0..(m-1)]$ 中齿诉。
模式的前綴函數(shù) $pi$ 包含模式與其自身的偏移進(jìn)行匹配的信息。這些信息可以用于在樸素的字符串匹配算法中避免對(duì)無(wú)用偏移進(jìn)行檢測(cè)，也可以避免在字符串匹配自動(dòng)機(jī)中粤剧，對(duì)整個(gè)轉(zhuǎn)移函數(shù) $\delta$ 的預(yù)先計(jì)算歇竟。如果q個(gè)字符已經(jīng)匹配成功，那么可以根據(jù)這q個(gè)已知的字符抵恋，我們能夠立即確定某些偏移是無(wú)效的焕议。

一個(gè)例子：

對(duì)于模式P=ababaca，目前已經(jīng)在T中匹配到了ababa弧关，q=5個(gè)字符已經(jīng)匹配成功盅安，同時(shí)發(fā)現(xiàn)T中的下一位不匹配。根據(jù)5個(gè)匹配字符的有用信息世囊，這里我們發(fā)現(xiàn) $P_3$ (aba)是P(ababaca)的最長(zhǎng)前綴的同時(shí)别瞭，也是 $P_5$ (ababa)的一個(gè)真后綴，即 $\pi[5]=3$ 株憾。在偏移s有q個(gè)字符成功匹配蝙寨，則下一個(gè)可能有效的偏移為 $s'=s+(q-\pi[q])$ 。

函數(shù)定義：

已知一個(gè)模式P[0..(m-1)]嗤瞎，模式P的前綴函數(shù)是函數(shù) $\pi:\ \{0,1,..,m-1\}\rightarrow\{0,1,..,m-1\}$ ,滿足
$\pi[q]=max\{k:k<q\ and\ P_k \sqsupset P_q \}$
即 $\pi[q]$ 是 $P_q$ 的真后綴P的最長(zhǎng)前綴長(zhǎng)度墙歪。

具體程序?qū)崿F(xiàn)：

vector<int> computePrefixFunc(string P){
    int m = P.size();
    vector<int> pi(m, 0);
    pi[0] = -1;
    int k = -1;
    for (int q = 1; q <= m - 1; q++){
        while (k > -1 && P[k + 1] != P[q])
            k = pi[k];
        if (P[k + 1] == P[q])
            k++;
        pi[q] = k;
    }
    return pi;
}
void kmpMatcher(string T, string P){
    int m = P.size();
    int n = T.size();
    vector<int> pi = computePrefixFunc(P);
    int k = -1;
    for (int i = 0; i < n; i++){
        while (k >-1 && P[k + 1] != T[i])//ptr和str不匹配，且k>-1（表示P和T有部分匹配）
            k = pi[k];//往前回溯
        if (P[k + 1] == T[i])
            k = k + 1;
        if (k == m - 1){ //說(shuō)明k移動(dòng)到ptr的最末端
            cout << i - m + 1 << endl;//返回相應(yīng)的位置
        }
    }
}
int main()
{
    string T("0201010102010");
    string P("0101020");
    kmpMatcher(T, P);
｝

該算法的預(yù)處理時(shí)間減少為 $\Theta(m)$ 贝奇，匹配時(shí)間為 $\Theta(n)$

最后編輯于：2018.10.15 16:30:45

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末虹菲，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子弃秆，更是在濱河造成了極大的恐慌，老刑警劉巖髓帽，帶你破解...
沈念sama閱讀 211,561評(píng)論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件菠赚，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡郑藏，警方通過(guò)查閱死者的電腦和手機(jī)衡查，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,218評(píng)論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)必盖，“玉大人拌牲，你說(shuō)我怎么就攤上這事「柚啵” “怎么了塌忽？”我有些...
開(kāi)封第一講書(shū)人閱讀 157,162評(píng)論 0贊 348
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)失驶。經(jīng)常有香客問(wèn)我土居，道長(zhǎng)，這世上最難降的妖魔是什么？我笑而不...
開(kāi)封第一講書(shū)人閱讀 56,470評(píng)論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任擦耀，我火速辦了婚禮棉圈，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘眷蜓。我一直安慰自己分瘾，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 65,550評(píng)論 6贊 385
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布吁系。她就那樣靜靜地躺著德召，像睡著了一般。火紅的嫁衣襯著肌膚如雪垮抗。梳的紋絲不亂的頭發(fā)上氏捞，一...
開(kāi)封第一講書(shū)人閱讀 49,806評(píng)論 1贊 290
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音冒版，去河邊找鬼液茎。笑死，一個(gè)胖子當(dāng)著我的面吹牛辞嗡，可吹牛的內(nèi)容都是我干的捆等。我是一名探鬼主播，決...
沈念sama閱讀 38,951評(píng)論 3贊 407
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼续室，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼栋烤！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起挺狰，我...
開(kāi)封第一講書(shū)人閱讀 37,712評(píng)論 0贊 266
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤明郭，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后丰泊，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體薯定，經(jīng)...
沈念sama閱讀 44,166評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,510評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年瞳购，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了话侄。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,643評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡学赛，死狀恐怖年堆，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情盏浇，我是刑警寧澤变丧，帶...
沈念sama閱讀 34,306評(píng)論 4贊 330
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站绢掰，受9級(jí)特大地震影響锄贷，放射性物質(zhì)發(fā)生泄漏译蒂。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,930評(píng)論 3贊 313
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一谊却、第九天我趴在偏房一處隱蔽的房頂上張望柔昼。院中可真熱鬧，春花似錦炎辨、人聲如沸捕透。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,745評(píng)論 0贊 21
一樁弒父案碴萧，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)乙嘀。三九已至，卻和暖如春破喻，著一層夾襖步出監(jiān)牢的瞬間虎谢，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 31,983評(píng)論 1贊 266
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工曹质，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留婴噩，地道東北人。一個(gè)月前我還...
沈念sama閱讀 46,351評(píng)論 2贊 360
代替公主和親
正文我出身青樓羽德，卻偏偏與公主長(zhǎng)得像几莽，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子宅静，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,509評(píng)論 2贊 348