#疯狂搜索（ POJ-1200） #哈希

题目

许多人喜欢解决难题，其中一些难题可能会使他们疯狂。一个这样的难题可能是在给定的文本中找到隐藏的素数。该数字可以是文本中存在的给定大小的不同子字符串的数量。您很快就会发现，您确实需要计算机的帮助和良好的算法来解决这一难题。
您的任务是编写一个程序，该程序给定子字符串的大小N，文本NC中可能出现的不同字符的数目以及文本本身，确定出现在字符串中的大小为N的不同子字符串的数目。文本。

例如，考虑N = 3，NC = 4和文本“ daababac”。在本文中可以找到大小为3的不同子字符串：“ daa”; “ aab”；“ aba”；“ bab”；“ bac”。因此，答案应该是5。
输入项
输入的第一行由两个数字N和NC组成，它们之间正好隔开一个空格。这之后是进行搜索的文本。您可以假设由可能的字符集形成的最大子字符串数不超过1600万。
输出量
程序应仅输出一个整数，该整数与在给定文本中找到的大小为N的不同子字符串的数量相对应。

.

Sample Input
3 4
daababac
Sample Output
5

答案

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int MaxNum=20000007;
string ch;
bool lage[MaxNum];
int hashArray[256];
int main(){
	int n, nc;
	cin>>n>>nc>>ch;
		int k=0;
		int len=ch.size();
		for(int i=0;i<len;i++){
			if(hashArray[ch[i]]==0){
				hashArray[ch[i]]=k++;//
			}
		}
		int ans=0;
		for(int i=0;i<=len-n;i++){
			int sum=0;
			for(int j=i;j<i+n;j++){
				sum=sum*nc+hashArray[ch[j]];//
			}
			if(!lage[sum]){
				ans++;
				lage[sum]=1;
			}
		}
		cout<<ans<<endl;
	
	return 0;
}