BF算法 c#實作

　　串的模式比對算法，主要對子串可進行固定位運算。常見的模式比對算法包括BF算法和KMP算法，其中BF算法是最直覺簡單的，但效率較低。KMP算法通過之前比對的結果進行合理的選擇下一步指針指向的位置。

1. BF算法

　　假設存在2個字元串S和T，其中S為主串，T為模式串，字元串對應的下标分别用i和j表示，判斷其是否比對。S=“abababcabcacbab”，T="abcac"。

　　BF模式比對中将主串和子串的第一個元素進行對比，如果相等，i和j各向後移動一位，即i=i+1,j=j+1。如果不相同，則i向後移動一位，模式串T從第一個字元開始進行對比判斷是否相同。

　　具體算法過程如下圖所示：

BF算法的c#實作如下所示：

static void Main(string[] args)
        {
            Char[] s = {\'a\',\'b\',\'a\',\'b\',\'c\',\'a\',\'b\',\'c\',\'a\',\'c\',\'b\',\'a\',\'b\'};
            Char[] t = { \'a\', \'b\', \'c\', \'a\', \'c\' };
            int result=BruteForce(s,t);
            Console.WriteLine("子串在主串中中比對的起始位置下标為：{0}", result);
            Console.Read();

        }
        /// <summary>
        /// 模式比對算法——BF算法
        /// 時間複雜度為：最好的情況O(n+m);最壞的情況：O(n*m)
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        public static int BruteForce(Char[] s,Char[] t)
        {
            if (s.Length == 0 || t.Length == 0)
                Console.WriteLine("請重新輸入字元串");
           int i=0;
           int j=0;
           int num = 0;
            if(i < s.Length)
            {
                while (j < t.Length)
                {
                    if (s[i] == t[j])
                    {
                        i++;
                        j++;
                    }
                    else
                    {
                        num++;
                        i = num;
                        j = 0;
                    }
                }
             }
            return i-t.Length;
        }

2. KMP算法

　　作者：海納

　　連結：https://www.zhihu.com/question/21923021/answer/281346746

　　來源：知乎

　　KMP算法的核心，是一個被稱為部分比對表(Partial Match Table)的數組。對于字元串“abababca”，它的PMT如下表所示：

char	a	b	a	b	a	b	c	a
index	1	2	3	4	5	6	7
value	1	2	3	4	1

　　就像例子中所示的，如果待比對的模式字元串有8個字元，那麼PMT就會有8個值。

　　我先解釋一下字元串的字首和字尾。如果字元串A和B，存在A=BS，其中S是任意的非空字元串，那就稱B為A的字首。例如，”Harry”的字首包括{”H”, ”Ha”, ”Har”, ”Harr”}，我們把所有字首組成的集合，稱為字元串的字首集合。同樣可以定義字尾A=SB，其中S是任意的非空字元串，那就稱B為A的字尾，例如，”Potter”的字尾包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然後把所有字尾組成的集合，稱為字元串的字尾集合。要注意的是，字元串本身并不是自己的字尾。

　　有了這個定義，就可以說明PMT中的值的意義了。PMT中的值是字元串的字首集合與字尾集合的交集中最長元素的長度。

　　以上述字元串為例說明計算其value值。

字元串	字首	字尾	value
a	null	null
ab	a	b
aba	{a,ab}	{ba,a}	1
abab	{a,ab,aba}	{bab,ab,b}	2
ababa	{a,ab,aba,abab}	{baba,aba,ba,a}	3
ababab	{a,ab,aba,abab,ababa}	{babab,abab,bab,ab,b}	4
abababc	{a,ab,aba,abab,ababa,ababab}	{bababc,ababc,babc,abc,bc,c}
abababca	{a,ab,aba,abab,ababa,ababab,abababc}	{bababca,ababca,babca,abca,bca,ca,a}	1

　　解釋清楚這個表之後，我們再來看如何使用這個表來加速字元串的查找及其原理。

　　如下圖所示，字元串進行比對時，如果在第J位不比對，那麼主串中S[i-j]~~S[i]位的元素與模式串中T[0]~~T[j-1]位相同。此時，下一步進行指針移動時，保持i指針不動，模式串T的指針後移至PMT[j-1]。

　　簡言之，以圖中的例子來說，在 i 處失配，那麼主字元串和模式字元串的前邊6位就是相同的。又因為模式字元串的前6位，它的前4位字首和後4位字尾是相同的，是以我們推知主字元串i之前的4位和模式字元串開頭的4位是相同的。就是圖中的灰色部分。那這部分就不用再比較了。(j移動的位數即next值)

　　有了上面的思路，我們就可以使用PMT加速字元串的查找了。我們看到如果是在 j 位失配，那麼影響 j 指針回溯的位置的其實是第 j −1 位的 PMT 值，是以為了程式設計的友善，我們不直接使用PMT數組，而是将PMT數組向後偏移一位。我們把新得到的這個數組稱為next數組。下面給出根據next數組進行字元串比對加速的字元串比對程式。其中要注意的一個技巧是，在把PMT進行向右偏移時，第0位的值，我們将其設成了-1，這隻是為了程式設計的友善，并沒有其他的意義。在本節的例子中，next數組如下表所示。

char	a	b	a	b	a	b	c	a
index	1	2	3	4	5	6	7
pmt	1	2	3	4	1
next	-1	1	2	3	4

求解next數組的具體過程如下：

j=1時，next[j]=0;

posted on

2019-01-11 15:39

竹影橫掃窗

閱讀(365)

評論(0)

編輯

舉報

BF算法 c#實作 - 竹影橫掃窗

1. BF算法

2. KMP算法