程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4821 杭州現場賽：每個片段字符串哈希比較

HDU 4821 杭州現場賽：每個片段字符串哈希比較

編輯：C++入門知識

HDU 4821 杭州現場賽：每個片段字符串哈希比較

I - String Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Practice HDU 4821

Description

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

思路：這題周賽的時候沒做出來，有點可惜了。要是當時記起來unsigned long long自動取模，然後提醒一下大帝的話，興許大帝就能過了。唉，導致讓他取了好多個模，最後還是WA了。太不機智了。范逗了。

這題我是從前面哈希的，看到題解中從後面哈希，就是不爽，所以自己從前面哈希。其實都一樣啦。

#include
#include
#include
#include
#include
#include
#include
#include
#define INF 100007
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
char s[100005];
ull base[100010],hash[100010];
int main()
{
    int m,l,i,j;//system("pause");
    for(i=1,base[0]=1;i<100001;i++)
        base[i]=base[i-1]*131ULL;
    while(~scanf("%d%d",&m,&l))
    {
        mapmm;
        scanf("%s",s);
        int sum=0,len=strlen(s);
        for(i=1,hash[0]=0;i<=len;i++)
            hash[i]=hash[i-1]*131+s[i-1]-'a'+1;
        for(i=0;i