字串匹配演算法 之BF、KMP

示例：

 1. 已知字串str1="acabaabaabcacaabc",求str2="abaabcac"是否在字串str1中？

 2. DNA病毒檢測，已知患者DNA序列求病毒DNA序列是否在患者DNA中出現過？病毒DNA為環狀結構（即首尾相連），

此文以問題1為例進行解答，

一、BF演算法：

即暴力檢測法，從字串第一個字符開始和匹配字串進行比較如果不同，則從字串第二個位置開始比較直到結束，

BF演算法思想很簡單，直接列出代碼實作：

 static void Main(string[] args)
        {
            string str = "acabaabaabcacaabc";//"aaabaaaaaab";
            string mo = "abaabc";//"aaaab";int flag;//表示查詢結果
            flag = BF(str, mo, 0);
            if (flag != -1) Console.WriteLine("匹配成功！" + "  下標為: " + flag);
            else Console.WriteLine("匹配失敗！");
        }

 private static int BF(string str, string mo, int v)
        {
            int i = v ,j = 0;
            while (i < str.Length && j < mo.Length)
            {
                if (str[i] == mo[j])
                {
                    i++;
                    j++;
                }
                else
                {
                    i = i - j + 1;
                    j = 0;
                }
            }
            if (j >= mo.Length) return i - mo.Length;
            else return -1;
        }

二、KMP演算法：

如圖：

在檢測中發現i和j標記的元素不同，此時如果是BF演算法直接ii= i-j+1,j = 0.但是KMP演算法思想是讓i下標不變，j下標變化，即可以理解為陣列str2右移盡可能少的單位，

問題來了，如何知道要移動多少呢?

 如圖，我們可以知道，在陣列str2中j下標之前的所有元素都和陣列str1的對應位匹配，那么我們只要保證，將str2陣列向右移動k，使得在str2中j=k元素之前的元素依舊匹配即可，因此引入

前綴和后綴的概念，前綴：元素的真子集 ，后綴：元素的反向真子集，即如aba三個元素，最長前綴為ab,最長后綴為ba，但是只有前綴a和后綴a相同所以str2的第四個元素的

next值為1；也就是當匹配到str[3]不同于str1時，此時j下標變為1即str2向右移動到j==下標1，

為此我們只需要根據str2得到next陣列就行，即得到str2的最大匹配前后綴個數，默認a[0]=0;即變化值為next值-1.因為next值是在字串下標從1開始，我們開發通常下標從0開始

 代碼如下：

 static void Main(string[] args)
        {
            string str = "acabaabaabcacaabc";//"aaabaaaaaab";
            string mo = "abaabc";//"aaaab";
            int[] next=new int[mo.Length];
            int flag;//表示查詢結果
            setNext(mo, next);
            foreach (var item in next)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
            flag = KMP(str, mo, 0, next);
            if (flag != -1) Console.WriteLine("匹配成功！" + "  下標為: " + flag);
            else Console.WriteLine("匹配失敗！");
        }

  private static void setNext(string mo, int[] next)
        {
            int i = 0, j = -1;
            next[0] = -1;
            while (i < mo.Length - 1)
            {
                if (j == -1 || mo[i] == mo[j])
                {
                    i++; j++;
                    next[i] = j;
                }
                else j = next[j];
            }
        }

   private static int KMP(string str, string mo, int v,int[] next)
        {
            int i = v, j = 0;
            while (i < str.Length && j < mo.Length)
            {
                if (j==-1 || str[i] == mo[j])
                {
                    i++;
                    j++;
                }
                else
                {
                    j = next[j];
                }
            }
            if (j >= mo.Length) return i - mo.Length;
            else return -1;
        }

 
//進一步對next陣列優化
private static void setNextVal(string mo, int[] next)
        {
            int i = 0, j = -1;
            next[0] = -1;
            while (i < mo.Length-1)
            {
                if (j == -1 || mo[i] == mo[j])
                {
                    i++; j++; 
                    if (mo[i] != mo[j]) next[i] = j;
                    else next[i] = next[j];
                }
                else j = next[j];
            }
        }

標籤：其他

上一篇：LeetCode python實作題解(持續更新)

下一篇：Microsoft 365 解決方案：未經身份驗證的用戶上載檔案小技巧 （2）