Rabin-Karp字符串匹配算法的滚动哈希

本文关键字：滚动 哈希 匹配算法 字符串 Rabin-Karp | 更新日期: 2023-09-27 18:17:30

这是Rabin-Karp字符串匹配算法在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 ";

我想检查它是否从第一个字符串复制，甚至我将添加一些东西在它或改变位置，但它不应该有区别，所以如何改变它，它只会比较字符串中的每个单词的哈希值，而不是实现它............

Rabin-Karp字符串匹配算法的滚动哈希

变化

string B = "Matches contains a pattern ";


string B = "contains a pattern ";

，它会起作用

相关文章：