题目地址：HDOJ 4821【String】
• 给定一个字符串S和两个整数L和M，我们称S的一个子串是“可恢复的”，当且仅当 • （i）子串的长度为ML； • （ii）这一子串通过串联S的M个“多样化”子串来构造：其中每个子串的长度L；而且这些子串不能有两个完全一样的串。 • 如果S的两个子串是从S的不同部分切下来的，则它们被认为是“不同的”。例如，字符串"aa"有3个不同的子串"aa"，“a"和"a”。 • 请您计算S的不同的“可恢复”子字符串的数量。 • 输入 • 输入包含多个测试用例，以EOF结束。 • 每个测试用例的第一行给出两个用空格分隔的整数M和L。 • 每个测试用例的第二行给出一个字符串S，它只包含小写字母。 • S的长度不大于10^5，而且1≤ML≤S的长度。 • 输出 • 对每个测试用例，在一行中输出答案。 • 输入样例
3 3 abcabcbcaabc• 输出样例
2题意： 一个字符串S 问其中有几个子串能满足以下条件： 1、长度为n*len 2、可以被分成n个len长的小串 每个串都不一样 思路： 通过字符串的hash，求出任意一个长度为L的子串的hash值。枚举字符串起始位置，从0枚举到L-1。然后，在这个位置开始，每L个字符作为一块，首先将前M块插入到map中，同时记录不相同字符串的个数，如果不相同字符串的个数是M，则满足要求。然后尺取，将这个区间向右移，删掉第1块，加入第M+1块，同样记录不相同字符串的个数。 字符串哈希模板 代码：
#include<iostream> #include<string.h> #include<algorithm> #include<map> using namespace std; typedef unsigned long long ULL; const int N = 1000010,base = 31; char str[N]; ULL h[N],p[N],tmp; int len,m,l,ans; map<ULL,int> mp; void makehash() { h[0] = 0,p[0] = 1; for(int i = 1;i <= len;i ++ ) { h[i] = h[i-1] * base + str[i] - 'a' + 1; p[i] = p[i-1] * base; } } ULL gethash(int l,int r)//获得 l 到 r 的 hash 值 { return h[r] - h[l - 1] * p[r - l + 1]; } int main() { while(~scanf("%d %d",&m,&l)) { scanf("%s",str + 1); len = strlen(str + 1); makehash(); ans = 0; for(int i = 1;i <= l && i + m*l <= len;i++) { mp.clear(); for(int j = i;j < i+m*l;j += l) { tmp = gethash(j,j+l-1); mp[tmp]++; } if(mp.size() == m) ans++; for(int j = i+m*l;j+l <= len+1;j += l) { tmp = gethash(j-m*l,j+l-1-m*l); mp[tmp]--; if(mp[tmp] == 0) mp.erase(tmp); tmp = gethash(j,j+l-1); mp[tmp]++; if(mp.size() == m) ans++; } } printf("%d\n",ans); } return 0; }