我的KMP算法實現有什麼問題？

Question

static void Main(string[] args) 
{ 
    string str = "ABC ABCDAB ABCDABCDABDE";//We should add some text here for 
              //the performance tests. 

    string pattern = "ABCDABD"; 


    List<int> shifts = new List<int>(); 

    Stopwatch stopWatch = new Stopwatch(); 

    stopWatch.Start(); 
    NaiveStringMatcher(shifts, str, pattern); 
    stopWatch.Stop(); 
    Trace.WriteLine(String.Format("Naive string matcher {0}", stopWatch.Elapsed)); 

    foreach (int s in shifts) 
    { 
     Trace.WriteLine(s); 
    } 

    shifts.Clear(); 
    stopWatch.Restart(); 

    int[] pi = new int[pattern.Length]; 
    Knuth_Morris_Pratt(shifts, str, pattern, pi); 
    stopWatch.Stop(); 
    Trace.WriteLine(String.Format("Knuth_Morris_Pratt {0}", stopWatch.Elapsed)); 

    foreach (int s in shifts) 
    { 
     Trace.WriteLine(s); 
    } 

    Console.ReadKey(); 
} 

static IList<int> NaiveStringMatcher(List<int> shifts, string text, string pattern) 
{ 
    int lengthText = text.Length; 
    int lengthPattern = pattern.Length; 

    for (int s = 0; s < lengthText - lengthPattern + 1; s++) 
    { 
     if (text[s] == pattern[0]) 
     { 
      int i = 0; 
      while (i < lengthPattern) 
      { 
       if (text[s + i] == pattern[i]) 
        i++; 
       else break; 
      } 
      if (i == lengthPattern) 
      { 
       shifts.Add(s);       
      } 
     } 
    } 

    return shifts; 
} 

static IList<int> Knuth_Morris_Pratt(List<int> shifts, string text, string pattern, int[] pi) 
{ 

    int patternLength = pattern.Length; 
    int textLength = text.Length;    
    //ComputePrefixFunction(pattern, pi); 

    int j; 

    for (int i = 1; i < pi.Length; i++) 
    { 
     j = 0; 
     while ((i < pi.Length) && (pattern[i] == pattern[j])) 
     { 
      j++; 
      pi[i++] = j; 
     } 
    } 

    int matchedSymNum = 0; 

    for (int i = 0; i < textLength; i++) 
    { 
     while (matchedSymNum > 0 && pattern[matchedSymNum] != text[i]) 
      matchedSymNum = pi[matchedSymNum - 1]; 

     if (pattern[matchedSymNum] == text[i]) 
      matchedSymNum++; 

     if (matchedSymNum == patternLength) 
     { 
      shifts.Add(i - patternLength + 1); 
      matchedSymNum = pi[matchedSymNum - 1]; 
     } 

    } 

    return shifts; 
} 

爲什麼我的KMP算法的實現工作比Naive String Matching算法慢？

Answer 1

KMP算法有兩個階段：首先建立一個表格，然後它執行搜索，由表格內容決定。

樸素算法有一個階段：它進行搜索。它在搜索階段的搜索效率低於，最壞的情況是。

如果KMP比天真算法慢，那麼這可能是可能是，因爲構建表比您花費的時間要長，而不是簡單地首先簡單搜索字符串。天真的字符串匹配通常是很短的字符串上很快。有一個原因是爲什麼我們在字符串搜索的BCL實現中不使用像KMP這樣的花式算法。在設置表格時，您可以使用樸素算法對六個短字符串進行六次搜索。

KMP是僅勝一場，如果你有巨大字符串和你正在做大量的搜索，讓您重新使用已經內置表。您需要通過使用該表進行大量搜索來分攤構建表的巨大成本。

此外，樸素算法在離奇和不太可能的情況下只有糟糕的表現。大多數人在像「白金漢宮，倫敦，英格蘭」等字符串中搜索像「倫敦」這樣的詞，而不是在像「BANAN BANANAN BANANANANANANANANAN ...」之類的字符串中搜索諸如「BANANANANANANA」之類的字符串。樸素搜索算法對於第一個問題是最優的，對於後一個問題是非常優化的;但對前者而不是後者進行優化是有意義的。

另一種說法：如果搜索字符串長度爲w，搜索字符串長度爲n，則KMP爲O（n）+ O（w）。 Naive算法是最壞情況O（nw），最好情況O（n + w）。但那沒有提到「恆定的因素」！ KMP算法的常數因子遠大於樸素算法的常數因子。 n的值必須非常大，並且次優部分匹配的數量必須非常大，因爲KMP算法贏得了快速樸素算法。

這涉及算法複雜性問題。你的方法也不是很好，這可能會解釋你的結果。記住，第一個當你運行代碼時，抖動必須將IL抖動成彙編代碼。 這可能需要比在某些情況下運行該方法更長的時間。你真的應該循環運行代碼數十萬次，丟棄第一個結果，並且取其餘的平均時間。

如果你真的想知道發生了什麼，你應該使用探查器來確定熱點是什麼。再一次，如果你想讓結果沒有被jit時間偏斜，那麼確保你正在測量post-jit運行，而不是運行的代碼被分析的地方。

Answer 2

您的示例太小，並且KMP避免回溯的模式沒有足夠的重複次數。

在某些情況下，KMP可能比正常搜索慢。

Answer 3

一個簡單的KMPSubstringSearch實現。

https://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/KMPSubstringSearch.cs

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace AlgorithmsMadeEasy 
{ 
    class KMPSubstringSearch 
    { 
     public void KMPSubstringSearchMethod() 
     { 
      string text = System.Console.ReadLine(); 
      char[] sText = text.ToCharArray(); 

      string pattern = System.Console.ReadLine(); 
      char[] sPattern = pattern.ToCharArray(); 

      int forwardPointer = 1; 
      int backwardPointer = 0; 

      int[] tempStorage = new int[sPattern.Length]; 
      tempStorage[0] = 0; 

      while (forwardPointer < sPattern.Length) 
      { 
       if (sPattern[forwardPointer].Equals(sPattern[backwardPointer])) 
       { 
        tempStorage[forwardPointer] = backwardPointer + 1; 
        forwardPointer++; 
        backwardPointer++; 
       } 
       else 
       { 
        if (backwardPointer == 0) 
        { 
         tempStorage[forwardPointer] = 0; 
         forwardPointer++; 
        } 
        else 
        { 
         int temp = tempStorage[backwardPointer]; 
         backwardPointer = temp; 
        } 

       } 
      } 

      int pointer = 0; 
      int successPoints = sPattern.Length; 
      bool success = false; 
      for (int i = 0; i < sText.Length; i++) 
      { 
       if (sText[i].Equals(sPattern[pointer])) 
       { 
        pointer++; 
       } 
       else 
       { 
        if (pointer != 0) 
        { 
         int tempPointer = pointer - 1; 
         pointer = tempStorage[tempPointer]; 
         i--; 
        } 
       } 

       if (successPoints == pointer) 
       { 
        success = true; 
       } 
      } 

      if (success) 
      { 
       System.Console.WriteLine("TRUE"); 
      } 
      else 
      { 
       System.Console.WriteLine("FALSE"); 
      } 
      System.Console.Read(); 
     } 
    } 
} 

/* 
* Sample Input 
abxabcabcaby 
abcaby 
*/