随笔-141  评论-9  文章-3  trackbacks-0

题意:统计由d个不同字符组成的串中,长度为n的不同字串数目。

分析:Rabin Karp

Rabin-Karp 算法(以下简称为 RK 算法),是基于这样的思路:即把串看作是字符集长度进制的数,由数的比较得出字符串的比较结果。例如,给定字符集为∑ ={0,1,2,3,4,5,6,7,8,9} ,∑长度为 d=10 ,那么任何以∑为字符集的串都可看作 d (此处为 10 )进制的数。

记模式串 P[0..n-1] 对应的数值为 P T[0..n-1] 所有长度为 m 的子串对应的数值为 ts ,设 P T 都是基于字符集长度为 | |=d 的字符串。

那么, ts 即为 T[s..s+m] 对应的数值,这里 0<=s<=n-m-1

P = P[m]+d*(P[m-1]+d*(P[m-2]+..)))

同样 t0 也可类似求得。

最重要的是如何从 ts 求出 ts+1

ts+1 =T[s+m]+d*(ts +dm-1 *T[s])

注:此处是该算法的关键,即在常数时间内能够计算出下一个 m 长度的字串对应的数值。初看比较抽象,举个例子就比较明白了,设 x=12345 ,现在是已知长度为 3 的数值 234 ,现在要求 345 对应的数值,可以这样来得到: 345 = 5 + 10*(234-102 *2)


#include <iostream>

using namespace std;

const int MAX = 100000000;

bool hash[MAX];
char text[MAX];
int key[256],c[10000], ans;

int main(){
    
int i, n,d,len;

    
//freopen("input.txt","r", stdin);

    scanf(
"%d%d"&n, &d);
    scanf(
"%s", text);
    len 
= strlen(text);
    
//init
    c[0]=1;
    
for(i=1; i<10000; i++)
        c[i] 
= c[i-1]*d;

    
int k=0;
    
for(i=0; i<len; ++i){
        
if(key[text[i]]==0)
            key[text[i]]
=k++;

        
if(k==d)
            
break;
    }


    
//sovle
    int h=0;
    
for(i=0; i<n; ++i)        
        h 
= h*+ key[text[i]];

    hash[h]
=true;
    ans
++;

    
for(i=0; i<len-n; ++i){
        h 
= d*(h-c[n-1]*key[text[i]]) + key[text[i+n]];
        
if(!hash[h]){
            hash[h]
=true;
            ans
++;
        }

    }


    printf(
"%d\n", ans);

    
return 0;
}

posted on 2011-03-16 00:08 小阮 阅读(305) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理