记忆碎片

今天抽时间看了下字符串的模式匹配，觉得算法导论上讲的还是蛮好的，rabin-karp算法，有限状态机算法，以及KMP算法，呵呵。想深入研究下rabin-karp算法，算法导论上面用了那么多的公式说明这个问题，其实这个算法就是有点使用hash的思想了。把模式字符串进行一个预处理，并mod，主字符串进行逐个进行简单的hash映射，然后mod比较…虽然最差是O(m(n-m+1)),一般情况下是O(m)次。

比如：子串“421″和源串”4234212456″

首先把423对某个质数取模，比如7，把模值和421对7取模的值进行对比。如果相同，则再用朴素算法逐字符对比，如果不同，把423变成234.可以通过(423-400)*10+4=234计算。其实对于任何位数的xyz（具体xyz是几位，要看子串的长度）都可以划分成(xyz-x*100)*10+m

其中m表示父串的下一位。这里的100是以子串长度为3来作比较的. 其中如果换成字符的话应该就是26了。

另外还在百度的时候就看到了POJ上一道题，大概也是这个思想啦。反正又是hash，现在感觉hash真是有用，要速度的地方到处都是它，呵呵。

花了一个多小时写了这道题，唉！有个很弱智的地方耗费了好大一会时间。

#include <stdio.h>
#include <stdlib.h>
#define  M  20000000
int hash[M];
char str[16000001];
int word_map[256],hash_add=0;
int n=0,nc=0;

int strhash(char * key)
{
	int i,h=0;
	for (i=0;i<n;i++)
	{
		h = h*nc + word_map[*(key + i)]; //just like the rabin-karp.
	}
	return h%M;
}
int main()
{
	int i=0,sizeNC=0,count=0,j;
	scanf("%d %d",&n,&nc);
	sizeNC = nc;
	scanf("%s",str);

	//init the map,we can not use the acsiic code
	while (sizeNC)
	{
		if (!word_map[str[i]])
		{
			word_map[str[i]] = sizeNC;
			sizeNC--;
		}
		i++;
	}

	// use the bash to count the words
	i=0;
//这里曾一度写成str[i+nc-1],害的我调了10几分钟，低级错误！
	while (str[i+n-1]!='\0')
	{
		hash_add = strhash(str+i);
		if (!hash[hash_add])
		{
			hash[hash_add]++;
			count++;
		}
		i++;
	}
	printf("%d\n",count);
}