pku 1200

2009年7月15日 星期三

题目链接：PKU 1200 Crazy Search

分类：字符串哈希

题目分析与算法模型
        本题是一个字符串哈希，即Rabin-Karp方法，该法算法导论中有介绍，就是将每个子字符串对应算出一个整数（该整数唯一标记字符串），然后统计asca数组存的是字符串中每个不同字母对应的一个值（0到N-1），采用N进制，本题中N即为nc，因为字母的ASCII码最大不会超过122，所以数组开到125足以，具体实现见代码，呵呵

Code：

 1#include <stdio.h>
 2#include <string.h>
 3int n,nc;
 4char str[20000000],asca[125];
 5int hash[16000005];
 6int main()
 7{
 8    while(scanf("%d%d",&n,&nc)!=EOF)
 9    {
10        scanf("%s",str);
11        int i=0,j,key=0,len=strlen(str),sum,cnt=0;
12        while(str[i])
13        {
14            if(asca[str[i]]==0) asca[str[i]]=key++;
15            i++;
16            if(key==nc) break;
17        }
18        for(i=0;i+n-1<len;i++)
19        {
20            sum=0;
21            for(j=i;j<=i+n-1;j++)sum=sum*nc+asca[str[j]];
22            if(hash[sum]==0) 
23            {
24                hash[sum]=1;
25                cnt++;
26            }
27        }
28        printf("%d\n",cnt);
29    }
30    return 0;
31}
32
33
34

posted on 2009-07-15 23:10 蜗牛也Coding 阅读(694) 评论(6)  编辑 收藏 引用

评论

# re: pku 1200 2009-09-01 09:54 chhaya

好办法！  回复  更多评论   

# re: pku 1200 2009-09-03 23:59 TBNB

你是怎么练出来的？  回复  更多评论   

# re: pku 1200 2009-09-04 00:06 TBNB

给初学者点儿建议啊？所谓达者兼济天下。  回复  更多评论   

# re: pku 1200 2009-09-04 01:09 蜗牛也Coding

@TBNB
自认为水平还没达到可以教别人的地步，如果实在要说，那只是：多做题，多看书，遇到实在不会的，参考别人的代码，理解其思想。
ACM的水很深.........要取得一定的成就必须付出几倍的辛勤.......  回复  更多评论   

# re: pku 1200 2011-03-13 18:35 litianxiu

int整型的数据是有范围的（大概小于10^12左右），如果超过范围怎么办？可能会有差错哦。就是说sum=sum*nc+a[str[j]];这条语句等于号左边的sum所算出的数据可能超过了int型的范围。

如果输入以下数据就会抛出异常：
12
15
123456789123456
  回复  更多评论   

# re: pku 1200 2011-12-25 10:51 satoshi

完全不需要存下字符串，每次读入一个字符处理即可  回复  更多评论   


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


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜