#include <stdio.h>
#include <string.h>
#include <math.h>

int main ()
{
	int		N, NC, count, value, h, d, i, len ;
	int		table[512], hashtable[16000000] ;
	char	text[1000000] ;

	while (scanf ("%d%d%s", &N, &NC, text) != EOF)
	{
		memset (table, 0xff, sizeof (table)) ;
		memset (hashtable, 0, sizeof (hashtable)) ;

		h = pow ((double) NC, (double) (N - 1)) ;
		d = NC ; //进制数
		count = 0 ;
		value = 0 ;//用来保存每个定长子串对应的整型值
		len = strlen (text) ;

		for (i = 0 ; i < len ; i++)  //将字符串中每个会出现的字符映射到一个整型值，这个整型值的范围是[0, NC - 1]
			if (table[text[i]] == -1)
				table[text[i]] = count++ ;

		for (i = 0 ; i < N ; i++)  //每个定长字串对应一个整型值，而且这个值的范围是[0, NC^N - 1]

			value = d * value + table[text[i]] ;

		hashtable[value] = 1 ;
		count = 1 ;

		for (i = 1 ; i + N - 1 < len ; i++)
		{
			value = d * (value - h * table[text[i - 1]]) + table[text[i + N - 1]] ;
			if (hashtable[value] == 0)
			{
				hashtable[value] = 1 ;
				count++ ;
			}
		}

		printf ("%d\n", count) ;
	}
	return 0 ;
}

• 原来是数组开太大，超过空间限制了！说是不超过16,000,000 。 要真开那么大还不行，开了8,000,000过了！ (0) ss08zhangchi 2010-01-24 02:24:46
  • Re:原来是数组开太大，超过空间限制了！说是不超过16,000,000 。 要真开那么大还不行，开了8,000,000过了！ (94) liustream 2010-03-14 21:14:35
• Re:本人用Karp-Rabin 和Hash, 各位看看为什么runtime error (1149) kaneLee 2010-03-06 06:55:20
• Re:本人用Karp-Rabin 和Hash, 各位看看为什么runtime error (11) zhanglistar 2014-10-13 22:31:08