beloved_ACM

SB，NB，都是一个B.
posts - 29, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

POJ_1200_RK算法

Posted on 2011-09-11 12:38 成幸毅 阅读(322) 评论(0)  编辑 收藏 引用
#include <iostream>
using namespace std;

int c[1000];
char s[10000000];
int ss[1000];
int key[1000];
bool hash[10000000];
int n,d;
int main() {
    
    while(scanf("%d%d",&n,&d)!= EOF) {
       
       memset(hash,0,sizeof(hash));
       scanf("%s",s);
       int len = strlen(s);
       c[0] = 1; 
       for(int i = 1; i < 100; i++)
          c[i] = c[i-1]*d;
       int k = 0;
       
       for(int i = 0; i < len; i++) {
          if(key[s[i]] == 0) 
             key[s[i]] = k++;
          if(k == d) break;
       }
       
       int h = 0;
       for(int i = 0; i < n; i++) {
          h = h*d + key[s[i]];
       }
       hash[h] = true;
       int ans = 1;
       for(int i = 0; i < len-n; i++) {
          h = d*h - key[s[i]]*c[n] + key[s[i+n]];
          if(!hash[h]) {
             hash[h] = true;
             ans++;
          } 
       }
       printf("%d\n",ans);
    }
   // system("pause");
    return 0;
}


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