HDU - 4821 String (长春市赛区I题)

HDU - 4821 String (长春赛区I题)

题意：求有多少个子串满足条件：

1. 长度为M*L

2. 每个长度为L的小子串不能都完全相同的情况

思路：当时没做出来，HASH处理，看了个思路是：

hash方法  设一个种子base  打表出nbase[i]表示base的i次方

从S最后一个字符开始打表  hash[i]=hash[i+1]*base+str[i]-'a'+1  即将i位以后的串hash成一个unsigned long long

然后每个len长度的小串的hash值即为  hash[i]-hash[i+len]*nbase[len]

最后使用map搞一下就可以AC

临摹了一个

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
typedef unsigned long long ull;
using namespace std;
const int MAXN = 100010;
const ull base = 31;

ull nbase[MAXN],hash[MAXN];
int n,len,ans,slen;
char str[MAXN];
map<ull, int> mp;

int main() {
	ull tmp;
	nbase[0] = 1;
	for (int i = 1; i <= MAXN; i++)
		nbase[i] = nbase[i-1] * base;
	while (scanf("%d%d", &n, &len) != EOF) {
		scanf("%s", str);
		slen = strlen(str);
		hash[slen] = 0;
		for (int i = slen-1; i >= 0; i--) 
			hash[i] = hash[i+1]*base+str[i]-'a'+1;
		ans = 0;
		for (int i = 0; i < len && i+n*len <= slen; i++) {
			mp.clear();
			for (int j = i; j < i+n*len; j += len) {
				tmp = hash[j] - hash[j+len]*nbase[len];
				mp[tmp]++;
			}
			if (mp.size() == n)
				ans++;
			for (int j = i+n*len; j+len <= slen; j += len) {
				tmp = hash[j-n*len] - hash[j-(n-1)*len]*nbase[len];
				mp[tmp]--;
				if (mp[tmp] == 0)
					mp.erase(tmp);
				tmp = hash[j] - hash[j+len]*nbase[len];
				mp[tmp]++;
				if (mp.size() == n)
					ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}