0

次の疑似コードに従って、C#.NET で Rabin-Karp アルゴリズムを実装しました。

疑似コード

問題は、パターンが元のテキストと一致しないことです。コードを徹底的に調べましたが、コードの問題を特定できません。誰かが私のコードのバグを見せてもらえますか?

static void Main(string[] args)
{
    string text = "ratcatpat catbats";
    string pattern = "cat";

    int d = text.Select(e => e).Distinct().Count();

    RabinCarp(text, pattern, d, 17);

    Console.ReadKey();
}

static void RabinCarp(string text, string pattern, int sizeOfAlphabet, int moduloValue)
{ 
    int rollingHashOf_P = 0;
    int rollingHashOf_T = 0;

    int lengthOfText = text.Length;
    int lengthOfPattern = pattern.Length;
    int h = (int)(Math.Pow(sizeOfAlphabet, lengthOfPattern - 1) % moduloValue);

    for (int i = 0; i < lengthOfPattern; i++)
    {
        rollingHashOf_P = (sizeOfAlphabet * rollingHashOf_P + (int)pattern[i]) % moduloValue;
        rollingHashOf_T = (sizeOfAlphabet * rollingHashOf_T + (int)text[i]) % moduloValue;
    }

    int diffNM = lengthOfText - lengthOfPattern;

    for (int i = 0; i <= diffNM; i++)
    {
        if (Math.Abs(rollingHashOf_P) == Math.Abs(rollingHashOf_T))
        {
            if (text.Substring(i, lengthOfPattern).Contains(pattern))
            {
                string message = "pattern identified";
                Console.WriteLine(message);
            }
        }   
        if (i < diffNM)
        {
            rollingHashOf_T = Math.Abs(sizeOfAlphabet * (rollingHashOf_T - (int)text[i] * h) + (int)text[i + lengthOfPattern]) % moduloValue;
        }
    }
}
4

1 に答える 1

2

私は Rabin-Karp アルゴリズムに精通していませんが、次のアルゴリズムとrollingHashOf_P同様に進める必要があると確信していrollingHashOf_Tます。

if (i < diffNM)
{
    rollingHashOf_T = Math.Abs(sizeOfAlphabet * (rollingHashOf_T - (int)text[i] * h) + (int)text[i + lengthOfPattern]) % moduloValue;
    rollingHashOf_P = Math.Abs(sizeOfAlphabet * (rollingHashOf_P - (int)pattern[i] * h) + (int)pattern[i + lengthOfPattern]) % moduloValue;
}

OPが以下のコメントでこの擬似コードを共有した後：

疑似コード

上記が間違っていることは明らかです。これを投稿のコードと比較すると、次のように、バグが最終的に進行中の行にある可能性があることが示されrollingHashOf_Tます。

rollingHashOf_T = Math.Abs(sizeOfAlphabet * (rollingHashOf_T - 
  (int)text[i] * h) + (int)text[i + lengthOfPattern]) % moduloValue;

疑似コードは、次のようにする必要があることを示唆していますが、

rollingHashOf_T = Math.Abs(sizeOfAlphabet * (rollingHashOf_T - 
  (int)text[i + 1] * h) + (int)text[i + lengthOfPattern + 1]) % moduloValue;
于 2014-04-17T20:21:33.947 に答える