HDU 4821 String 題解：字符串哈希與滑動窗口統計固定長度子串出現次數

題目大意

給定字符串 s 長度 n，參數 m, l。將字符串按模 l 分為 l 組，每組位置為 i, i+l, i+2l...。對每組滑動窗口長度 m（即覆蓋 m 個子串），檢查窗口內 m 個長度為 l 的子串是否互不相同。統計滿足條件的窗口數。n ≤ 100000。

哈希方案

多項式滾動哈希：H[i] = H[i+1]*Seed + (s[i]-'a'+1)，Seed=31（質數）。子串 [i, i+l-1] 哈希值：H[i] - H[i+l]*Seed^l。預計算 Seed^l。

滑動窗口處理

對每個偏移 offset = 0..l-1：

1. 提取該組所有子串哈希值。
2. 維護大小 m 的滑動窗口，用 HashMap 計數。
3. 若窗口內 map.size() == m（所有哈希值不同），答案++。
4. 滑動：移除最舊，添加最新，更新 map。

關鍵代碼 (C++)

ULL H[100010], K; char s[100010];
int main() {
    int m, l;
    while (scanf("%d%d",&m,&l)!=EOF) {
        scanf("%s",s);
        int n=strlen(s);
        for (int i=n-1;i>=0;--i) H[i]=H[i+1]*Seed+(s[i]-'a'+1);
        for (K=Seed,int i=2;i<=l;++i) K*=Seed; // Seed^l
        int ans=0;
        for (int offset=0; offset mp;
            for (int j=offset; j