c - ラビン-カープ文字列検索アルゴリズム

Question

私の以前の質問は、一般的な文字列検索アルゴリズムに関するものでした。私はラビン-カープアルゴリズムを研究していて、次のような関数テンプレートを持っています。

RabinKarpMatch(char *Text, char *Search_phrase,int radix,int prime)

search_phraseとtextに応じて、基数と素数の値がどのように変化するか知りたいですか？それとも、すべての場合に任意の値を指定する必要がありますか？

Answer 1

Rabin-Karpアルゴリズムでは、基数と素数はテキスト処理中に変更されません。しかし、適切な基数と素数を選択することは非常に重要です。最悪の場合（実際にはほとんど不可能）、テキストのすべてのサブストリングがテンプレートハッシュコードと等しい同じハッシュコードを持っている場合、アルゴリズムはO（nm）時間で機能します。ここで、nはテキストの長さ、mはテンプレートの長さです。

一般的な規則：Prime-は小さく、基数-は使い勝手が良い必要があります。私は次のようなペアを信じています：

（プライム、基数）

31、2 ^ 64

37、2 ^ 64

57、2 ^ 64

大丈夫です。

一部の実装では、ハッシュの衝突を最小限に抑えるために、複数のペアが使用されます。

Answer 2

import java.util.*;
import java.lang.*;

// Rabin Karp
// find if pattern exists in string or not. If found return its index.

public class RabinKarp {

    private int prime = 101;

    public int patternSearch(String s, String pattern) {

        int lengthOfPattern = pattern.length();
        long hashOfPattern = createHash(pattern, lengthOfPattern);
        long hashOfString = createHash(s, lengthOfPattern);

        for(int i = 0; i < s.length() - lengthOfPattern + 1; i++) {

            if (hashOfPattern == hashOfString && checkEqual(pattern, s.substring(i, i + lengthOfPattern), lengthOfPattern))
                return i;
            if (i != s.length() - lengthOfPattern)
                hashOfString = reCreateHash(s.substring(i+1,i+1+lengthOfPattern), hashOfString, (int)s.charAt(i), lengthOfPattern);
        }
        return -1;
    }

    public boolean checkEqual(String pattern,String substring,int end){
        for (int i=0;i<end;i++)
            if (pattern.charAt(i) != substring.charAt(i))
                return false;
        return true;
    }

    public long reCreateHash(String pattern, long oldHash, int oldCharAsciiValue, int end) {
        long hash = 0;
        hash = oldHash - oldCharAsciiValue;
        hash = hash / prime;
        hash += pattern.charAt(end-1) * Math.pow(prime, end - 1);
        return hash;
    }

    public long createHash(String pattern,int end) {
        long hash = 0L;
        for(int i = 0; i < end; i++)
            hash += pattern.charAt(i) * Math.pow(prime, i);
        return hash;
    }

    public static void main(String arg[]){
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a String");
        String s = sc.nextLine();
        System.out.println("Enter a pattern");
        String pattern = sc.nextLine();
        RabinKarp rk = new RabinKarp();
        System.out.println("Staring index of pattern is " + rk.patternSearch(s, pattern));
    }
}

Answer 3

ラビンカープ文字列照合アルゴリズム
コード：

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <math.h>
#define d 10
void RabinKarpStringMatch(char*, char*, int);
void main()
{
    char *Text, *Pattern;
    int Number = 11; //Prime Number
    clrscr();
    printf("\nEnter Text String : ");
    gets(Text);
    printf("\nEnter Pattern String : ");
    gets(Pattern);

    RabinKarpStringMatch(Text, Pattern, Number);
    getch();
}

void RabinKarpStringMatch(char* Text, char* Pattern, int Number)
{
    int M, N, h, P = 0, T = 0, TempT, TempP;
    int i, j;
    M = strlen(Pattern);
    N = strlen(Text);
    h = (int)pow(d, M - 1) % Number;
    for (i = 0; i < M; i++) {
        P = ((d * P) + ((int)Pattern[i])) % Number;
        TempT = ((d * T) + ((int)Text[i]));
        T = TempT % Number;
    }
    for (i = 0; i <= N - M; i++) {
        if (P == T) {
            for (j = 0; j < M; j++)
                if (Text[i + j] != Pattern[j])
                    break;
            if (j == M)
                printf("\nPattern Found at Position: %d", i + 1);
        }
        TempT = ((d * (T - Text[i] * h)) + ((int)Text[i + M]));
        T = TempT % Number;
        if (T < 0)
            T = T + Number;
    }
}

コードの出力