| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 21585 | Accepted: 6101 |
Description
Input
Output
Sample Input
3 4 daababac
Sample Output
5
思路：利用Karp-Rabin算法的思想，对每个子串进行Hash，如果Hash值相等则认为这两个子串是相同的（事实上还需要做进一步检查），Karp-Rabin算法的Hash函数有多种形式，但思想都是把字符串映射成一个数字。本题hash函数是把字串转化为NC进制的数（实际上程序中计算结果已经被转换为10进制，因为NC进制数不同转化为10进制数自然不同，所以不影响判断结果），数组开到了1.6×10^7（我试了一下1.2×10^7也能AC）,实际上这也是不严谨的，因为我们不能保证hash之后的数值在这个范围内，比如N=NC=35,程序就有Bug了，但是这题后台数据可能没这么给。在实际运用中是需要取模的，而且即使hash值相等也需要进一步比对。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 bool hash[16000005]; 6 int is_have[300]; 7 char str[1000005]; 8 int main(){ 9 int n, nc; 10 /* freopen("in.c", "r", stdin); */ 11 while(~scanf("%d%d", &n, &nc)){ 12 memset(str, 0, sizeof(str)); 13 memset(hash, 0, sizeof(hash)); 14 memset(is_have, 0, sizeof(is_have)); 15 scanf("%s", str); 16 int len = strlen(str); 17 int k = 0, ans = 0; 18 for(int i = 0;i < len;i ++) is_have[str[i]] = 1; 19 for(int i = 0;i < 256;i ++) 20 if(is_have[i]) is_have[i] = k++; 21 for(int i = 0;i <= len - n;i ++){ 22 int key = 0; 23 for(int j = i;j < i + n;j ++) key = key*nc + is_have[str[j]]; 24 if(!hash[key]) ans ++, hash[key] = 1; 25 } 26 printf("%d\n", ans); 27 } 28 return 0; 29 }
下面附上一般情况的实现代码(均来自其他网友）：
1. 原文链接：http://www.xefan.com/archives/83853.html
1 #include <stdio.h> 2 #include <math.h> 4 int mod = 0x7fffffff; 5 const int d = 128; 7 int rabin_karp(char *T, char *P, int n, int m) 8 { 9 if (n < m) return -2; 10 int h = pow(d, m-1); 11 int p = 0; 12 int t = 0; 13 int i, j; 14 for (i=0; i<m; i++) { 15 p = (d*p + P[i]) % mod; 16 t = (d*t + T[i]) % mod; 17 } 18 for (j=0; j<=n-m; j++) { 19 if (p == t) { 20 return j; 21 } 22 if (j < n-m) { 23 t = (d*(t - h*T[j]) + T[j+m]) % mod; 24 } 25 } 26 return -1; 27 } 28 29 int main(int argc, char *argv[]) 30 { 31 char t[] = "BBC ABCDAB ABCDABCDABDE"; 32 char p[] = "ABCDABD"; 33 int len1 = sizeof(t) - 1; 34 int len2 = sizeof(p) - 1; 35 int index = rabin_karp(t, p, len1, len2); 36 printf("index: %d\n", index); 37 return 0; 38 }
2.
原文链接：http://blog.csdn.net/onezeros/article/details/5531354
1 //Karp-Rabin algorithm,a simple edition 2 int karp_rabin_search(const char* text,const int text_len,const char* pattern,const int pattern_len) 3 { 4 int hash_text=0; 5 int hash_pattern=0; 6 int i; 7 8 //rehash constant:2^(pattern_len-1) 9 int hash_const=1; 10 /*for (i=1;i<pattern_len;i++){ 11 hash_const<<=1; 12 }*/ 13 hash_const<<=pattern_len-1; 14 15 //preprocessing 16 //hashing 17 for (i=0;i<pattern_len;++i){ 18 hash_pattern=(hash_pattern<<1)+pattern[i]; 19 hash_text=(hash_text<<1)+text[i]; 20 } 21 22 //searching 23 for (i=0;i<=text_len-pattern_len;++i){ 24 if (hash_pattern==hash_text&&memcmp(text+i,pattern,pattern_len)==0){ 25 return i; 26 }else{ 27 //rehash 28 hash_text=((hash_text-text[i]*hash_const)<<1)+text[i+pattern_len]; 29 } 30 } 31 return -1; 32 }
POJ --- 1200 Crazy Search,布布扣,bubuko.com
原文：http://www.cnblogs.com/anhuizhiye/p/3649953.html