pku1200.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 59 行

#include <stdio.h>
int char_key[130];
char s[1000000];
int HashTable[510000];
int N, NC;

int hashCode(int k)
{
	int i, code = 0;
	for (i = 0; i < N; i++)
	{
		code *= NC;
		code += char_key[s[i + k]];
	}
	return code;
}

int Insert(int k)
{
	int i, code;
	code = hashCode(k);
	if ((HashTable[code / 32] & 1 << (code % 32)) == 0)
	{
		HashTable[code / 32] |= 1 << (code % 32);
		return 1;
	}
	return 0;
}

int main()
{
	int cnt, l, kk, i;
	scanf("%d%d", &N, &NC);
	scanf("%s", s);
	
	l = 0;
	kk = 0;
	memset(char_key, -1, sizeof(char_key));
	memset(HashTable, 0, sizeof(HashTable));
	while (s[l] != '\0')
	{
		if (char_key[s[l]] == -1)
		{
			char_key[s[l]] = kk;
			kk++;
		}
		l++;
	}
	for (i = 0, cnt = 0; i <= l - N; i++)
	{
		if (Insert(i) == 1)
		{
			cnt++;
		}
	}
	printf("%d\n", cnt);
	return 0;
}