演算法字元串

① 數據結構與演算法——字元串匹配問題(KMP演算法)

KMP演算法也是比較著名的模式匹配演算法。是由 D.E.Knuth,J.H.Morrs 和 VR.Pratt 發表的一個模式匹配演算法。可以大大避免重復遍歷的情況。

如果使用暴風演算法的話，前面五個字母完全相等，直到第六個字母 "f" 和 "x" 不相等。如下圖：

T = 「abcdex」
j 123456
模式串 abcdex
next[j] 011111

T = "abcabx"
j 123456
模式串T abcabx
next[j] 011123

T = "ababaaaba"
j———————123456789
模式串T——— ababaaaba
next[j]————011234223

T = "aaaaaaaab"
j———————123456789
模式串T——— aaaaaaaab
next[j]————012345678

next數組其實就是求解字元串要回溯的位置
假設，主串S= 「abcababca」;模式串T=「abcdex」，由以上分析得出next數組為011111，next數組意味著當主串與模式串不匹配時，都需要從第一個的位置重新比較。

KMP演算法也是有缺陷的，比如主串S=「aaaabcde」,模式串T= 「aaaaax」。next的數組就是012345；

當開始匹配時，當i= 5，j = 5時，我們發現字元"b"與字元「a」不相等，如上圖，j = next[5] = 4;

由於T串的第二、三、四、五位置的字元都與首位「a」相等，那麼可以用首位next[1]的值去取代與它相等的後續字元的next[j],那麼next數組為{0,0,0,0,0,5};

在求解nextVal數組的5種情況

② 字元串匹配演算法的使用（未完待整理）

字元串的匹配在java中都知道使用indexOf函數來實現，那麼其匹配演算法是怎麼樣的呢？

單模式和多模式的區別就是一次遍歷主串能否將多個模式的字元串都查找出來。

英文全稱為Brute Force，暴力匹配演算法，匹配字元串的方法比較暴力，也比較簡單易懂。其大概的思路就是：

我們可以看到，在極端情況下，在主串 aaaa...aab 中尋找模式串 aab ，那麼總共需要尋找(n-m+1)次，且每次都需要比對m次，那麼時間復雜度將是 (n-m+1)*m ，即 O(n*m) ；但實際上並不會這么低效，因為我們的使用場景中主串和模式串都不會太長，而且在每個子串和模式串進行比對時，只要中途有一個不匹配，那麼當前比對就會提前結束，因此大部分情況下，時間復雜度都會比 O(n*m) 要好。

我們在BF演算法的基礎上引入哈希演算法，我們不需要將每個子串與模式串逐個字元地進行比較，而是計算得出每個子串的hash值，然後和模式串的hash值進行比較，如果有相等的，那就說明有子串和模式串匹配上了。

雖然我們只需要比對模式串和子串的hash值就能得到匹配結果，次數為(n-m+1)，但是對每個子串進行hash計算的時候，是要遍歷每個字元的，因此次數也是m，那麼總的時間復雜度還是 O(n*m) ，並沒有明顯地提升。

那麼我們該如何想出一個辦法，使得每個子串hash值的計算時間得到提升呢？這就是RK演算法的精髓，假設子串包含的字元集中元素個數為k，那麼就用k進制數來代表這個子串，然後hash的過程就是將這個k進制的數轉換為十進制的數，這個十進制的數就是該子串的hash值。

相鄰子串的hash值計算是有規律的，我們只需要遍歷一次主串就能得到所有子串的hash值，演算法復雜度為O(n)，而不是像原先一樣，每個子串都需要O(m)的時間復雜度。

然後將模式串的hash值和所有子串的hash值進行比較，每次比較的時間復雜度是 O(1) ，總共比較(n-m+1)次，所以RK演算法的總的時間開銷為 O(n)+O(1)*O(n-m+1) ，即為 O(n) ，時間復雜度比BF演算法更加高效。

當然，有hash的地方就有可能會存在hash沖突，有可能子串和hash值和模式串的hash值是一樣的，但內容就是不一樣，此時怎麼辦呢？其實很簡單，對於hash值一樣的子串，我們增加雙保險，再比較一下這m個字元是否都一樣即可，總的時間開銷為 O(n)+O(1)*O(n-m+1)+O(m) ，即為 O(n) 。

如果極端情況下出現了很多hash沖突呢？我們對於每個和模式串相同hash值的子串都需要逐一再進行比較，那麼總的時間開銷就會為 O(n)+O(1)*O(n-m+1)+O(m)*O(n-m+1) ，即為 O(n*m) ，不過這種概率太小了，大部分情況下都不會這樣。

在真正的文本編輯器中查找和替換某個字元串時，使用的演算法既不是上述的BF演算法，也不是RK演算法；BF演算法只適合不是很長的主串，RK演算法則要設計一個沖突概率很低的hash演算法，這個比較困難，所以實際使用的是BM演算法，它是工程中非常常用的一種字元串匹配演算法，效率也是最高的。

演算法的思想和過程有些復雜，待以後整理。

KMP演算法在本質上是和BM演算法一樣的。演算法的思想和過程有些復雜，待以後整理。

瀏覽器輸入框中的智能輸入匹配是怎麼實現的，它是怎麼做動態字元串匹配查找的呢？這就用到了Trie樹。

又名字典樹，是一種專門用來快速查找字元串前綴匹配結果的樹形結構，其本質就是將所有字元串的重復的前綴合並在一起，構造一個多叉樹。

其中，根節點不包含任何信息，每個節點表示一個字元，從根節點到紅色節點的一條路徑表示存儲的一個字元串。當我們在如上Trie樹中查找"he"時，發現"he"並非是一個字元串，而是"hello"和"her"的公共前綴，那麼就會找到這兩個字元串返回。

Trie樹在內存中是如何存儲的呢？因為每一個節點都可能是包含所有字元的，所以每一個節點都是一個數組（或者散列表），用來存儲每個字元及其後綴節點的指針。

使用Trie樹，最開始構建的時候，時間復雜度為 O(n) ，其中n為所有字元串長度之和，但是一旦構建完成，頻繁地查詢某個字元串是非常高效的，時間復雜度為 O(k) ，其中k為查找字元串的長度。

Trie樹雖然查詢效率很高，但是比較浪費內存，每一個節點都必須維護一個數組存放所有可能的字元數據及其指向下一個節點的指針，因此在所有字元串公共前綴並不多的時候，內存空間浪費地就更多了。這種問題其實也有對應的解決辦法，我們可以不使用數組，而是使用有序數組、散列表、紅黑樹來存放，可以相應地降低性能來節省內存空間。

Trie樹除了可以實現瀏覽器動態輸入內容查找候選項的功能外，還可以實現多模式地敏感詞匹配功能。假設我們需要對用戶輸入的內容進行敏感詞檢查，將所有的敏感內容用***代替，那麼該如何實現呢？

首先我們可以維護一個敏感詞字典，使用上述四種單模式匹配演算法也可以實現，但是需要遍歷N次用戶輸入的內容，其中N是所有敏感詞的模式串，顯得非常低效。但是我們如果將敏感詞字典維護為一個Trie樹，然後將用戶輸入的內容從位置0開始在Trie樹中進行查詢，如果匹配到紅色節點，那麼說明有敏感詞；如果沒有匹配到紅色節點，就從用戶輸入內容的下一個位置開始繼續在Trie樹中查詢，直至將用戶輸入內容遍歷完，因此我們只是遍歷了一遍主串。

然而更高效的多模式字元串匹配使用地更多的是如下的AC自動機。

如果把Trie樹比作BF演算法，KMP演算法是BF演算法的改進，那麼AC自動機就是利用同樣的思想改進了Trie樹。

演算法的思想和過程有些復雜，待以後整理。

③ 面試必備——BM字元串查找演算法

字元串的一種基本操作是子字元串查找：給定一端長度為N的文本字元串text和一個長度為M(M<N)的模式字元串pattern，在文本字元串中查找和該模式字元串相同的子字元串。在這互聯網時代，字元串查找的需求在很多情景都需要，如在文本編輯器或瀏覽器查找某個單詞、在通信內容中截取感興趣的模式文本等等。

子字元串查找最簡單的實現肯定是暴力查找：

可以看到，暴力查找的最壞時間復雜度為O(N*M)，實際應用中往往文本字元串很長（成萬上億個字元），而模式字元串很短，這樣暴力演算法的時間復雜度是無法接受的。

為了改進查找時間，人們發明了很多字元串查找演算法，而今天的主角 BM演算法 （Bob Boyer和J Strother Moore發明，簡稱BM演算法）就是其中的一種。

不同於暴力查找演算法的逐個字元對比，BM演算法充分使用 預處理模式字元串 的信息來盡可能跳過更多的字元。在暴力演算法中，比較一個字元串都是從首字母開始，逐個比較下去。一旦發現有不同的字元，就需要從頭開始進行下一次比較，就需要將字串中的所有字元一一比較。BM演算法的核心思路在於，文本字元串從左到右檢索，模式字元串從右到左檢索，當模式字元串的一個字元pattern[j]和文本字元串的字元text[i+j]不匹配時，那麼在模式字元串中查找字元text[i+j]是否存在索引k，使得pattern[k] == text[i+j]，k若存在， k應該為滿足條件的最右索引 。此時存在三種情景：

通過這種字元的移動方式來代替逐個比較，正是BM演算法的高效的關鍵所在！那麼我們怎麼知道文本字元串的字元是否存在於模式字元串中？對的，預處理。我們在查找前，先建立一張包含文本字元串的所有字元的字母表， 這張表中記錄著字母表中的每個字元在模式字元串中出現的最靠右的索引，如果在字元在模式字元串中不存在，那麼值為-1。

有了這張表，我們在查找時就可以高效的移動i。構建這張表很簡單：

構建好表，我們只需要按上面分析的情景，出現字元不匹配時，通過表，把i向右平移到具體位置即可。BM完整演算法實現如下：

由於不匹配的情況屬於大多數，所以一般情況下，BM演算法的時間復雜度為O(N/M)，是線性級別的！可以說是非常高效了。但它需要額外的空間字母表大小R，所以BM演算法是以空間換時間的。

至此，BM字元串查找演算法已經分析完了，其實算是一種比較簡單的演算法，學習起來很快就能搞懂～

面試必備——KMP字元串查找演算法

④ 字元串匹配演算法

boyermoore演算法的sample程序

TCHAR * BoyerMooreSearch(TCHAR *sSrc, TCHAR *sFind)
{
//
// 聲明：
// 該段代碼只是BoyerMoore(名字也許不準確)的基本思想，當
// 然不是最優的，具體完善工作就留給你自己樂！嘻嘻。
// 該演算法的本質就是從字元串的右端而不是左端開始比較，這
// 樣，當查詢不匹配時才有可能直接躍過多個字元（最多可以躍過
// strlen(sFind)個字元），如果最右邊的字元匹配則回溯。比如：
//
// pain
// ^ 這是第一次比較n和空格比
// The rain in SpainThe rain in Spain
//
// pain
// ^ 這是第二次比較，好爽呀！
// The rain in SpainThe rain in Spain
//
// 當然，這樣比較會產生一些問題，比如：
//
// pain
// ^ （圖1）
// The rain in SpainThe rain in Spain
//
// 如果比較到這兒，大家都會看到，只需再向後移到兩個字元
// 就匹配成功了，但如果接下去還按上面的方法跳strlen(sFind)的
// 話，就會錯過一次匹配！！！！！
//
// pain
// ^
// The rain in SpainThe rain in Spain
//
// 怎麼辦？當然可以解決！大家回頭看圖1，當時a是pain的子
// 串，說明有可能在不移動strlen(sFind)的跨度就匹配成功，那就
// 人為地給它匹配成功的機會嘛！串一下pain串，直接讓兩個a對齊
// 再做比較！呵呵，如果要比較的字元不是pain的子串，當然就可
// 以直接跨過strlen(sFind)個字元了！不知我說明白沒？
//
//

// 查詢串的長度
int nLenOfFind = lstrlen(sFind);
// 被查詢串的長度
int nLenOfSrc = lstrlen(sSrc);
// 指向查詢串最後一個字元的指針
TCHAR * pEndOfFind = sFind + nLenOfFind -1;
// 指向被查詢串最後一個字元的指針
TCHAR * pEndOfSrc = sSrc + nLenOfSrc -1;

// 在比較過程中要用到的兩個指針
TCHAR * pSrc = sSrc;
TCHAR * pFind;

// 總不能一直讓它比較到win.com文件的地址去吧？嘻嘻！
while ( pSrc <= pEndOfSrc ) {

// 每次匹配都是從右向左，這是本演算法的核心。
pFind = pEndOfFind;

// 如果比較不成功，被查詢串指針將向右串的字元數
int nMoveRightSrc;

// 比較被查詢串的當前字元是否和查詢串的最右邊字
// 符匹配，如果匹配則回溯比較，如果全匹配了，該
// 干什麼，我就不用說了吧？:-)
while ( pFind >= sFind ) {

// TNND，白廢功夫比了！看看需要向右移動幾個
// 字元吧（如果說從右到左是本演算法的核心，則
// 判斷向右移幾個字元則是本演算法的技巧）。
if ( *pSrc != *pFind ) {

// 被查詢串的當前字元是否在查詢串里？
TCHAR * p = strrchr( sFind, *pSrc );
// 沒在，直接移lstrlen(sFind)個字元
if ( NULL == p )
nMoveRightSrc = nLenOfFind;
else
// 哇塞！真的在，那就只需...
nMoveRightSrc = pEndOfFind - p;

break;
}

// 哈！又匹配成功了一個！接著向左回溯...
pFind --;
pSrc --;
}

// 如果在上面的while循環里每一次比較都匹配了
// 那就對了唄！告訴用戶找到了
if ( pFind < sFind )
return ( pSrc + 1 );

// 沒匹配成功，nMoveRightSrc上面已經算好了
// 直接用就可以了。
pSrc += nMoveRightSrc;
}

// 程序運行到這兒肯定是沒指望了！
return NULL;
}

行了，函數寫完了，我們可以試一下了！

void CTNNDDlg::OnButton1()
{
TCHAR sSrc[] = "The rain in Spain";
TCHAR sFind[]= "pain";

TCHAR * pFound = BoyerMooreSearch( sSrc, sFind );
if ( pFound )
MessageBox(pFound);
else
MessageBox("沒找到");
}

//另外一個
void preBmBc(char *x, int m, int bmBc[]) {
int i;

for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}

void suffixes(char *x, int m, int *suff) {
int f, g, i;

suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}

void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];

suffixes(x, m, suff);

for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}

void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE];

/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);

/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
OUTPUT(j);
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}

⑤ 【演算法筆記】字元串匹配

BF 演算法中的 BF 是 Brute Force 的縮寫，中文叫作暴力匹配演算法，也叫樸素匹配演算法：

主串和模式串：
在字元串 A 中查找字元串 B，那字元串 A 就是主串，字元串 B 就是模式串。我們把主串的長度記作 n，模式串的長度記作 m

我們在主串中，檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串匹配的。

BF 演算法的時間復雜度是 O(n*m)

等價於

比如匹配Google 和Goo 是最好時間復雜度，匹配Google 和ble是匹配失敗的最好時間復雜度。

KMP演算法是一種改進的字元串匹配演算法，由D.E.Knuth與J.H.Morris和V.R.Pratt同時發現，因此人們稱它為克努特—莫里斯—普拉特演算法。KMP演算法主要分為兩個步驟：字元串的自我匹配，目標串和模式串之間的匹配。

看來網上很多的文章，感覺很多的都沒有說清楚，這里直接復制阮一峰的內容，講的很清晰
內容來自 http://www.ruanyifeng.com/blog/

首先，字元串"BBC ABCDAB ABCDABCDABDE"的第一個字元與搜索詞"ABCDABD"的第一個字元，進行比較。因為B與A不匹配，所以搜索詞後移一位。

因為B與A不匹配，搜索詞再往後移。

就這樣，直到字元串有一個字元，與搜索詞的第一個字元相同為止。

接著比較字元串和搜索詞的下一個字元，還是相同。

直到字元串有一個字元，與搜索詞對應的字元不相同為止。

這時，最自然的反應是，將搜索詞整個後移一位，再從頭逐個比較。這樣做雖然可行，但是效率很差，因為你要把"搜索位置"移到已經比較過的位置，重比一遍。

一個基本事實是，當空格與D不匹配時，你其實知道前面六個字元是"ABCDAB"。KMP演算法的想法是，設法利用這個已知信息，不要把"搜索位置"移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。

怎麼做到這一點呢？可以針對搜索詞，算出一張《部分匹配表》（Partial Match Table）。這張表是如何產生的，後面再介紹，這里只要會用就可以了。

已知空格與D不匹配時，前面六個字元"ABCDAB"是匹配的。查表可知，最後一個匹配字元B對應的"部分匹配值"為2，因此按照下面的公式算出向後移動的位數：

因為 6 - 2 等於4，所以將搜索詞向後移動4位。

因為空格與C不匹配，搜索詞還要繼續往後移。這時，已匹配的字元數為2（"AB"），對應的"部分匹配值"為0。所以，移動位數 = 2 - 0，結果為 2，於是將搜索詞向後移2位。

因為空格與A不匹配，繼續後移一位。

逐位比較，直到發現C與D不匹配。於是，移動位數 = 6 - 2，繼續將搜索詞向後移動4位。

逐位比較，直到搜索詞的最後一位，發現完全匹配，於是搜索完成。如果還要繼續搜索（即找出全部匹配），移動位數 = 7 - 0，再將搜索詞向後移動7位，這里就不再重復了。

下面介紹《部分匹配表》是如何產生的。

首先，要了解兩個概念："前綴"和"後綴"。 "前綴"指除了最後一個字元以外，一個字元串的全部頭部組合；"後綴"指除了第一個字元以外，一個字元串的全部尾部組合。

"部分匹配值"就是"前綴"和"後綴"的最長的共有元素的長度。以"ABCDABD"為例，

"部分匹配"的實質是，有時候，字元串頭部和尾部會有重復。比如，"ABCDAB"之中有兩個"AB"，那麼它的"部分匹配值"就是2（"AB"的長度）。搜索詞移動的時候，第一個"AB"向後移動4位（字元串長度-部分匹配值），就可以來到第二個"AB"的位置。

BM（Boyer-Moore）演算法。它是一種非常高效的字元串匹配演算法，有實驗統計，它的性能是著名的KMP 演算法的 3 到 4 倍。

BM 演算法包含兩部分，分別是壞字元規則（bad character rule）和好後綴規則（good suffix shift）

未完待續

參考文章：
字元串匹配的Boyer-Moore演算法

⑥ 【演算法】字元串移位

問題：一個字元串可以由另一個字元串移位得到，例如 abcd ，可以由 bcad 移位得到。

這個問題表面上說的是字元串，但是其實更進一步可以理解為兩個字元數組的元素是否一致。最簡單和直白的方式，無異於用兩層循環的方式來進行循環判斷。這是常規方案一。

還有方案二，則是需要用到數據結構，例如，將一個字元串轉換成一個set。循環另一個數組，往set中插入數據，如果一直是失敗的，則true。有一次插入成功了，則false。

如果我們在轉換一下思想，字元其實在計算機中的表現，它的實質上也是數字畢碧，比如ASCII碼中，字元 a 是可以轉換成數字97的，所以兩個數衫物組其實只要求元素之間的差的和，如果等於0就可以判斷是或數液否相等。
例如：
1,2,34 和 2,3,14
則：

差的和：

但是，這樣只是判斷了移位，並沒有判斷基準位置。比如， 13 和 22 是可以判斷成立的，因此需要增加判斷兩個數組的乘積是否相等。來判斷基準位置是否一致。

我所寫實現依賴於ASCII碼，當如果字元串是Unioncode編碼的字元，則就會出現問題。容我有空去研究一下，相處通用得解決方案。 如有問題歡迎各位批評指正，不勝感激。

⑦ 字元串演算法之模式字元刪除

根據慧沖顫一個給定模式，刪除模式中出現的字元，如模式為「aeiou」，則」google」，刪除後變為ggl。

考慮最優效率，我們可以先建立一個哈希表，以可能出現的字元ASCII碼作為索引，遍歷模式中的字元，將相應位置賦值為1。判空再遍歷源字元串，如果源字元串中的字元出現在哈希表中，則去掉該字元。這樣時間復雜度為O(n)。

def patterndelete(astr,pstr):

    hashtable=[0]*256

    for i in range(len(pstr)):

        hashtable[ord(pstr[i])]=1

    retstr=''

    for i in range(len(astr)):

        if hashtable[ord(astr[i])]!=1:

            retstr=retstr+astr[i]

return retstr

    前敗   測試用例

>>> patterndelete('weouthdgd','aeiou')

'wthdgd'

>>> patterndelete('weouthdgd','a')   

'weouthdgd'

>>> 

⑧ （演算法）去除字元串中的重復字元（時間復雜度）

1.一般會想到遍歷字元串，鉛好辯去除重復的字元，這樣時間復雜度是O(n²)，時間復雜度太高。

static String sub(String str){

StringBuffer result =newStringBuffer();

List list =new ArrayList();

char[] cs = str.toCharArray();

for(int i=0; i<cs.length; i++){

if(!list.contains(cs[i])){

result.append(cs[i]);

list.add(cs[i]);

}

}

returnresult.toString();

}

2.再仔細想一想

用java的String的indexOf方法來達到字元串去重的目的，indexOf的功能是返回指定字元在此字元串中第一次出現處的索引：

public static String QuChong(String str){

        StringBuilder sb=new StringBuilder();

        for(int i=0;i<str.length();i++){

            if(str.indexOf(str.charAt(i))==i){

                //第一次出槐缺現

                sb.append(str.charAt(i));

            }

        }

        String result=sb.toString();

       襪畢 return result;

    }

⑨ 演算法：判斷兩個字元串是否包含相同的字元

方坦模鋒法一： 最笨的方法，循環遍歷，可以把字元串轉化為數組，然後排序，然後比較。function : compare1
方法二： 以空間換取時間, 把兩個字元串分別轉換為字元數組，然後另外i用一個數組str，每個元素初始化為0，然後遍歷第一個字元數組，減字元『0』可得到其對應的ASCII碼從而轉化為整數n，把str數組的第n個元素加1， 然後遍歷第二個字元數組進行同樣的操作，只是第n個元素不是加1而是減1， 這樣若是str數組有元素為0，則說明兩個字元串讓晌有相同的字元。function : compare2
方法三： 方法二的延伸，利用map的特點，先把第一個字元串的每一個字元作為key插入，再插入第二個字元串的每一個字元，map的key是唯一的，如果不能插入，則表明此字元在第一個字元串中存在。
下面是方法一和方法碼空二的java實現，方法三還在測試中。