HDU4821 String（字符串哈希）

题目描述

Given a string S and two integers L and M, we consider a substring of S as “recoverable” if and only if (i) It is of length M*L; (ii) It can be constructed by concatenating M “diversified” substrings of S, where each of these substrings has length L; two strings are considered as “diversified” if they don’t have the same character for every position. Two substrings of S are considered as “different” if they are cut from different part of S. For example, string “aa” has 3 different substrings “aa”, “a” and “a”. Your task is to calculate the number of different “recoverable” substrings of S.

Input

The input contains multiple test cases, proceeding to the End of File. The first line of each test case has two space-separated integers M and L. The second ine of each test case has a string S, which consists of only lowercase letters. The length of S is not larger than 10^5, and 1 ≤ M * L ≤ the length of S.

Output

For each test case, output the answer in a single line.

Sample Input 3 3 abcabcbcaabc Sample Output 2

题目大意

给你一个字符串s。问最多能找出多少个符合要求的子串。 要求：1.该子串长度为m*l。2.将该子串分割为m个长度为l的子串，要求这m个子串互不相同。

题目分析

这个题思路其实也不难。枚举s中所有长度为m*l的子串。 再将这个子串分割为m个长度为l的字符串，再通过map+字符串哈希判断这m个子串中有没有重复。

但这样做的时间复杂度过高，因此我们还需要进一步优化： 当枚举某一个位置的m*l字符串时，当判断完毕之后，我们可以先不向后枚举，而是删去开头的长度为l的子串，而在字符串末尾加上后面的一个长度为l的子串。这样就是一种新的情况，重复这个操作直到字符串后面剩的字符不到l个为止。 这样就可以把外圈循环的次数控制在l之内了。 在判断过程中将所有符合条件的记录下来，最后输出即可。

代码如下

#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <map> #include <queue> #include <vector> #include <set> #include <algorithm> #include <iomanip> #define ULL unsigned long long #define PII pair<int,int> using namespace std; const int N=1e5+5,P=131; char s[N]; ULL p[N],h[N]; //记录哈希值 map<ULL,int> ma; //用map来判断是否存在重复 ULL get(int l,int r) //计算字符串[l,r]区间内的哈希值 { return h[r]-h[l-1]*p[r-l+1]; } int main() { int l,m; while(~scanf("%d %d",&m,&l)) //多组输入 { scanf("%s",s+1); int len=strlen(s+1); p[0]=1; for(int i=1;i<=len;i++) //计算哈希值 { h[i]=h[i-1]*P+s[i]; p[i]=p[i-1]*P; } int ans=0; //记录符合要求的子串数量 for(int i=1;i+l*m<=len&&i<=l;i++) //枚举s的所有l*m的子串 { ma.clear(); //清空map for(int j=i;j<i+l*m;j+=l) //判断当前串的情况 { ULL key=get(j,j+l-1); ma[key]++; } if(ma.size()==m) ans++; //如果map中有m个元素，说明没有重复，符合要求 for(int j=i+m*l;j+l<=len+1;j+=l) //向后查找新的字符串（看上面的优化说明） { ULL key=get(j-m*l,j-m*l+l-1); //去掉开头的长度为l的子串 ma[key]--; if(ma[key]==0) ma.erase(key); key=get(j,j+l-1); //在末尾添加新的长度为l的子串 ma[key]++; if(ma.size()==m) ans++; } } printf("%d\n",ans); } return 0; }