我之前的问题是关于一般字符串搜索算法的。我正在研究Rabin-Karp算法,我有一个函数模板,如:
RabinKarpMatch(char *Text, char *Search_phrase,int radix,int prime)
我想知道基数和素数的值将如何根据search_phrase和text改变?还是应该给它们任意的值?
在Rabin-Karp算法中,基数和素数在文本处理过程中不会改变。但是选择好的基数和质数是至关重要的。在最坏的情况下(在实践中几乎不可能),当文本的所有子字符串具有与模板哈希码相同的哈希码时,算法将在O(nm)时间内工作,其中n是文本长度,m是模板长度。
一般规则:素数-必须小,基数-必须方便使用。我相信像这样的组合:
('基数)2 ^ 6431日
37岁的2 ^ 64
57岁2 ^ 64
可以。
在一些实现中,为了最小化哈希冲突,使用了多个哈希对。
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));
}
}
RABIN KARP字符串匹配算法
代码:
#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;
}
}
代码输出