拉賓，卡普串通過滾動散列

這裏匹配算法是用C＃拉賓，卡普字符串匹配算法的實現...拉賓，卡普串通過滾動散列

static void Main(string[] args) 
{ 
    string A = "String that contains a pattern."; 
    string B = "pattern"; 
    ulong siga = 0; 
    ulong sigb = 0; 
    ulong Q = 100007; 
    ulong D = 256; 
for (int i = 0; i < B.Length; i++) 
{ 
    siga = (siga * D + (ulong)A[i]) % Q; 
    sigb = (sigb * D + (ulong)B[i]) % Q; 
} 
if (siga == sigb) 
{ 
    Console.WriteLine(string.Format(">>{0}<<{1}", A.Substring(0, B.Length), A.Substring(B.Length))); 
    return; 
} 
ulong pow = 1; 
for (int k = 1; k <= B.Length - 1; k++) 
    pow = (pow * D) % Q; 

for (int j = 1; j <= A.Length - B.Length; j++) 
{ 
    siga = (siga + Q - pow * (ulong)A[j - 1] %Q) % Q; 
    siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q; 
    if (siga == sigb) 
    { 
     if (A.Substring(j, B.Length) == B) 
     { 
      Console.WriteLine(string.Format("{0}>>{1}<<{2}", A.Substring(0, j), 
                  A.Substring(j, B.Length), 
                  A.Substring(j +B.Length))); 
      return; 
     } 
    } 
} 
Console.WriteLine("Not copied!");

}

，但如果我改變位置有一個問題第二個字符串比它顯示的結果不會被複制，但

string A = "String that contains a pattern."; 
string B = "pattern";

此處顯示不可複製

string A = "String that contains a pattern."; 
string B = "Matches contains a pattern ";

我想檢查它是否從第一個字符串複製或甚至我會添加一些東西在它或改變位置，但它不應該有所作爲，所以如何改變它，它只是比較每個哈希值詞串比實現它............

來源

2011-12-12 Rdx

變化

string B = "Matches contains a pattern ";

到

string B = "contains a pattern ";

，它會工作

來源

2011-12-12 16:44:47

但這不是一個解決方案如果我使用兩個輸入文件，並希望檢查他們和第二個文件正在編輯通過改變它的位置每個和一切都在那裏，但它被複制，所以我們如何檢查這個?????? ??????? – Rdx

在這種情況下，你有什麼是不夠的。檢查http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm#Rabin.E2.80.93Karp_and_multiple_pattern_search – 2011-12-12 17:10:37

拉賓，卡普串通過滾動散列

回答

相關問題