Go語言 排序與搜索切片

Go語言標(biāo)準(zhǔn)庫中提供了sort包對整型，浮點(diǎn)型，字符串型切片進(jìn)行排序，檢查一個(gè)切片是否排好序，使用二分法搜索函數(shù)在一個(gè)有序切片中搜索一個(gè)元素等功能。

創(chuàng)新互聯(lián)是一家專業(yè)提供咸豐企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、H5響應(yīng)式網(wǎng)站、小程序制作等業(yè)務(wù)。10年已為咸豐眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站制作公司優(yōu)惠進(jìn)行中。

關(guān)于sort包內(nèi)的函數(shù)說明與使用，請查看

在這里簡單講幾個(gè)sort包中常用的函數(shù)

在Go語言中，對字符串的排序都是按照字節(jié)排序，也就是說在對字符串排序時(shí)是區(qū)分大小寫的。

二分搜索算法

Go語言中提供了一個(gè)使用二分搜索算法的sort.Search(size,fn)方法：每次只需要比較㏒?n個(gè)元素，其中n為切片中元素的總數(shù)。

sort.Search(size,fn)函數(shù)接受兩個(gè)參數(shù)：所處理的切片的長度和一個(gè)將目標(biāo)元素與有序切片的元素相比較的函數(shù)，該函數(shù)是一個(gè)閉包，如果該有序切片是升序排列，那么在判斷時(shí)使用 有序切片的元素 = 目標(biāo)元素。該函數(shù)返回一個(gè)int值，表示與目標(biāo)元素相同的切片元素的索引。

在切片中查找出某個(gè)與目標(biāo)字符串相同的元素索引

數(shù)據(jù)結(jié)構(gòu)與算法——字符串匹配問題(KMP算法)

KMP算法也是比較著名的模式匹配算法。是由 D.E.Knuth,J.H.Morrs 和 VR.Pratt 發(fā)表的一個(gè)模式匹配算法?？梢源蟠蟊苊庵貜?fù)遍歷的情況。

如果使用暴風(fēng)算法的話，前面五個(gè)字母完全相等，直到第六個(gè)字母 "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數(shù)組其實(shí)就是求解字符串要回溯的位置

假設(shè)，主串S= “abcababca”;模式串T=“abcdex”，由以上分析得出next數(shù)組為011111，next數(shù)組意味著當(dāng)主串與模式串不匹配時(shí)，都需要從第一個(gè)的位置重新比較。

KMP算法也是有缺陷的，比如主串S=“aaaabcde”,模式串T= “aaaaax”。next的數(shù)組就是012345；

當(dāng)開始匹配時(shí)，當(dāng)i= 5，j = 5時(shí)，我們發(fā)現(xiàn)字符"b"與字符“a”不相等，如上圖，j = next[5] = 4;

由于T串的第二、三、四、五位置的字符都與首位“a”相等，那么可以用首位next[1]的值去取代與它相等的后續(xù)字符的next[j],那么next數(shù)組為{0,0,0,0,0,5};

在求解nextVal數(shù)組的5種情況

字符串匹配算法是怎么算的？

這是一個(gè)畢業(yè)老師出的字符串的算法的題目！這是答案 可以參考一下！ boyermoore算法的sample程序 TCHAR * BoyerMooreSearch(TCHAR *sSrc, TCHAR *sFind) { // // 聲明： // 該段代碼只是BoyerMoore(名字也許不準(zhǔn)確) 的基本思想，當(dāng) // 然不是最優(yōu)的，具體完善工作就留給你自己樂！嘻嘻。 // 該算法的本質(zhì)就是從字符串的右端而不是左端開始比較，這 // 樣，當(dāng)查詢不匹配時(shí)才有可能直接躍過多個(gè)字符（最多可以躍過 // strlen(sFind)個(gè)字符）， 如果最右邊的字符匹配則回溯。比如： // // pain // ^ 這是第一次比較n和空格比 // The rain in SpainThe rain in Spain // // pain // ^ 這是第二次比較，好爽呀！ // The rain in SpainThe rain in Spain // // 當(dāng)然，這樣比較會產(chǎn)生一些問題，比如： // // pain // ^ （圖1） // The rain in SpainThe rain in Spain // // 如果比較到這兒，大家都會看到，只需再向后移到兩個(gè)字符 // 就匹配成功了，但如果接下去還按上面的方法跳strlen( sFind)的 // 話，就會錯(cuò)過一次匹配！?。。?！ // // pain // ^ // The rain in SpainThe rain in Spain // // 怎么辦？當(dāng)然可以解決！大家回頭看圖1，當(dāng)時(shí)a是pain的子 // 串，說明有可能在不移動(dòng)strlen(sFind) 的跨度就匹配成功，那就 // 人為地給它匹配成功的機(jī)會嘛！串一下pain串， 直接讓兩個(gè)a對齊 // 再做比較！呵呵，如果要比較的字符不是pain的子串，當(dāng)然就可 // 以直接跨過strlen(sFind)個(gè)字符了！ 不知我說明白沒？ // // // 查詢串的長度 int nLenOfFind = lstrlen(sFind); // 被查詢串的長度 int nLenOfSrc = lstrlen(sSrc); // 指向查詢串最后一個(gè)字符的指針 TCHAR * pEndOfFind = sFind + nLenOfFind -1; // 指向被查詢串最后一個(gè)字符的指針 TCHAR * pEndOfSrc = sSrc + nLenOfSrc -1; // 在比較過程中要用到的兩個(gè)指針 TCHAR * pSrc = sSrc; TCHAR * pFind; // 總不能一直讓它比較到 win.com 文件的地址去吧？嘻嘻！ while ( pSrc = pEndOfSrc ) { // 每次匹配都是從右向左，這是本算法的核心。 pFind = pEndOfFind; // 如果比較不成功，被查詢串指針將向右串的字符數(shù) int nMoveRightSrc; // 比較被查詢串的當(dāng)前字符是否和查詢串的最右邊字 // 符匹配，如果匹配則回溯比較，如果全匹配了，該 // 干什么，我就不用說了吧？:-) while ( pFind = sFind ) { // TNND，白廢功夫比了！看看需要向右移動(dòng)幾個(gè) // 字符吧（如果說從右到左是本算法的核心，則 // 判斷向右移幾個(gè)字符則是本算法的技巧）。 if ( *pSrc != *pFind ) { // 被查詢串的當(dāng)前字符是否在查詢串里？ TCHAR * p = strrchr( sFind, *pSrc ); // 沒在，直接移lstrlen(sFind)個(gè)字符 if ( NULL == p ) nMoveRightSrc = nLenOfFind; else // 哇塞！真的在，那就只需... nMoveRightSrc = pEndOfFind - p; break; } // 哈！又匹配成功了一個(gè)！接著向左回溯... pFind --; pSrc --; } // 如果在上面的while循環(huán)里每一次比較都匹配了 // 那就對了唄！告訴用戶找到了 if ( pFind sFind ) return ( pSrc + 1 ); // 沒匹配成功，nMoveRightSrc上面已經(jīng)算好了 // 直接用就可以了。 pSrc += nMoveRightSrc; } // 程序運(yùn)行到這兒肯定是沒指望了！ return NULL; } 行了，函數(shù)寫完了，我們可以試一下了！ void CTNNDDlg::OnButton1() { TCHAR sSrc[] = "The rain in Spain"; TCHAR sFind[]= "pain"; TCHAR * pFound = BoyerMooreSearch( sSrc, sFind ); if ( pFound ) MessageBox(pFound); else MessageBox("沒找到"); } //另外一個(gè) 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 個(gè)子串，看有沒有跟模式串匹配的。

BF 算法的時(shí)間復(fù)雜度是 O(n*m)

等價(jià)于

比如匹配Google 和Goo 是最好時(shí)間復(fù)雜度，匹配Google 和ble是匹配失敗的最好時(shí)間復(fù)雜度。

KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth與J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)，因此人們稱它為克努特—莫里斯—普拉特算法。KMP算法主要分為兩個(gè)步驟：字符串的自我匹配，目標(biāo)串和模式串之間的匹配。

看來網(wǎng)上很多的文章，感覺很多的都沒有說清楚，這里直接復(fù)制阮一峰的內(nèi)容，講的很清晰

內(nèi)容來自

首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一個(gè)字符與搜索詞"ABCDABD"的第一個(gè)字符，進(jìn)行比較。因?yàn)锽與A不匹配，所以搜索詞后移一位。

因?yàn)锽與A不匹配，搜索詞再往后移。

就這樣，直到字符串有一個(gè)字符，與搜索詞的第一個(gè)字符相同為止。

接著比較字符串和搜索詞的下一個(gè)字符，還是相同。

直到字符串有一個(gè)字符，與搜索詞對應(yīng)的字符不相同為止。

這時(shí)，最自然的反應(yīng)是，將搜索詞整個(gè)后移一位，再從頭逐個(gè)比較。這樣做雖然可行，但是效率很差，因?yàn)槟阋?搜索位置"移到已經(jīng)比較過的位置，重比一遍。

一個(gè)基本事實(shí)是，當(dāng)空格與D不匹配時(shí)，你其實(shí)知道前面六個(gè)字符是"ABCDAB"。KMP算法的想法是，設(shè)法利用這個(gè)已知信息，不要把"搜索位置"移回已經(jīng)比較過的位置，繼續(xù)把它向后移，這樣就提高了效率。

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

已知空格與D不匹配時(shí)，前面六個(gè)字符"ABCDAB"是匹配的。查表可知，最后一個(gè)匹配字符B對應(yīng)的"部分匹配值"為2，因此按照下面的公式算出向后移動(dòng)的位數(shù)：

因?yàn)?6 - 2 等于4，所以將搜索詞向后移動(dòng)4位。

因?yàn)榭崭衽cC不匹配，搜索詞還要繼續(xù)往后移。這時(shí)，已匹配的字符數(shù)為2（"AB"），對應(yīng)的"部分匹配值"為0。所以，移動(dòng)位數(shù) = 2 - 0，結(jié)果為 2，于是將搜索詞向后移2位。

因?yàn)榭崭衽cA不匹配，繼續(xù)后移一位。

逐位比較，直到發(fā)現(xiàn)C與D不匹配。于是，移動(dòng)位數(shù) = 6 - 2，繼續(xù)將搜索詞向后移動(dòng)4位。

逐位比較，直到搜索詞的最后一位，發(fā)現(xiàn)完全匹配，于是搜索完成。如果還要繼續(xù)搜索（即找出全部匹配），移動(dòng)位數(shù) = 7 - 0，再將搜索詞向后移動(dòng)7位，這里就不再重復(fù)了。

下面介紹《部分匹配表》是如何產(chǎn)生的。

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

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

"部分匹配"的實(shí)質(zhì)是，有時(shí)候，字符串頭部和尾部會有重復(fù)。比如，"ABCDAB"之中有兩個(gè)"AB"，那么它的"部分匹配值"就是2（"AB"的長度）。搜索詞移動(dòng)的時(shí)候，第一個(gè)"AB"向后移動(dòng)4位（字符串長度-部分匹配值），就可以來到第二個(gè)"AB"的位置。

BM（Boyer-Moore）算法。它是一種非常高效的字符串匹配算法，有實(shí)驗(yàn)統(tǒng)計(jì)，它的性能是著名的KMP 算法的 3 到 4 倍。

BM 算法包含兩部分，分別是壞字符規(guī)則（bad character rule）和好后綴規(guī)則（good suffix shift）

未完待續(xù)

參考文章：

字符串匹配的Boyer-Moore算法