Hash

Description

给定长度为 n （ n<=1000000）的字符串，字符串仅由小写字母的前 m （ m<=6）个字符组成，请你计算出共有多少长度为 k（ k<=6）的不相同子串。

Input

第一行输入包括 n、 m、 k 三个数字，接下来一行输入长度为 n 的字符串

Output

输出长度为 k 的不相同字串的数量。

Sample Input

8 2 3ababaaab

Sample Output

HINT

样列中不同的子串分别为 aba、 bab、 baa、 aaa、 aab。

思路

将每个子串分别映射为一个整数，然后sort一遍，查找共有多少个不同的hash值即可。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn =1000005;
int num[maxn];
char a[maxn],str[10];

int IndexHash(char *key)
{
    int hashval = 0;
    while (*key != '\0')    hashval = (hashval<<5) + *key++;
    return hashval;
}

int main()
{
    //freopen("data.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int n,m,k,i,p = 0;
    memset(str,0,sizeof(str));
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s",a);
    for (i = 0;i <= n - k;i++)
    {
        strncpy(str,a + i,k);
        int hashval = IndexHash(str);
        num[p++] = hashval;
    }
    sort(num,num+p);
    int res = 1;
    for (i = 1;i < p;i++)
    {
        if (num[i] != num[i-1]) res++;
    }
    printf("%d\n",res);
    return 0;
}

对拍程序

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<map>
#include<string>
using namespace std;
const int maxn = 1000000;

int main()
{
	freopen("data.txt","w",stdout);
	srand(time(NULL));
	int n,m,k;
	n = maxn,m = 5,k = 5;
	printf("%d %d %d\n",n,m,k);
	while (n--)
	{
		printf("%c",rand()%m+'a');
	}
	printf("\n");
	return 0;
}

字符

数据结构作业——hash(字符串哈希）