Rabin-Karp文字列検索アルゴリズム学習:poj 1200

もともとHashを勉強しようとしたが、PPTが言った最初のアルゴリズムが文字列処理に関連しているのを見て、もともとHashの中にも文字列Hashを専門に話しているものがあるので、「アルゴリズム導論」の分類に従って、これを「文字列処理」に分けましょう.
Rabin-Karpアルゴリズムの思想は超簡単です:d個の異なるアルファベットの文字列を1つのd進数に変換します.得られたこの数字が多すぎると1つの質量数をモデリングすることができるが、複数の文字列の数値が同じになる可能性があるため、素朴なアルゴリズムで判断することができる(1対1で比較する).(以下より抜粋:
 http://skyhacker.ixiezi.com/2010/12/20/poj1200-crazysearchrabin-karp/)
POJの上の問題に対して簡単です!

  
  
  
  

   
   
   
   
#include<stdio.h> 
   
   
   
   
 #include<string.h> 
   
   
   
   
 /* 
   
   
   
   
  * Rabin-Karp       ：    NC             NC     
   
   
   
   
  * */ 
   
   
   
   
 #define MM 16000005 
   
   
   
   
 char s[MM]; 
   
   
   
   
 int hash[MM]; 
   
   
   
   
 int asc[128]; 
   
   
   
   
  
   
   
   
   
 // NC       10     
   
   
   
   
 int n,nc; 
   
   
   
   
 void init(){ 
   
   
   
   
    memset(asc,0,sizeof(asc)); 
   
   
   
   
    memset(hash,0,sizeof(hash)); 
   
   
   
   
 } 
   
   
   
   
 // NC        10     
   
   
   
   
 void solve(){ 
   
   
   
   
    int ans=0; 
   
   
   
   
    int len=strlen(s); 
   
   
   
   
    //                   
   
   
   
   
    for(int i=0,j=0;i<len;i++){ 
   
   
   
   
        if(!asc[s[i]])asc[s[i]]=j++; 
   
   
   
   
        if(j==nc)break; 
   
   
   
   
    } 
   
   
   
   
    //      hash   
   
   
   
   
    int key; 
   
   
   
   
    for(int i=0;i<len-n+1;i++){ 
   
   
   
   
        key=0; 
   
   
   
   
        for(int j=i;j<i+n;j++)key+=key*nc+asc[s[j]]; 
   
   
   
   
        if(!hash[key])hash[key]=1,ans++; 
   
   
   
   
    } 
   
   
   
   
    printf("%d
",ans); 
   
   
   
   
 } 
   
   
   
   
 int main(){ 
   
   
   
   
    scanf("%d %d",&n,&nc); 
   
   
   
   
    scanf("%s",s); 
   
   
   
   
    init(); 
   
   
   
   
    solve(); 
   
   
   
   
 } 

  
  
  
  

    ：
http://www.ituring.com.cn/article/1759  http://www.cnblogs.com/Jason-Damon/archive/2012/03/31/2426745.html