题目分析

我们需要处理一个长度最大为 $16000000$ 的字符串，并计算其哈希值。为了减少哈希冲突和计算量，我们可以将字符串视为一个 $nc$ 进制的数字，其中 $nc$ 是字符集的大小（即不同字符的数量）。每个字符的权值由其首次出现的顺序决定。

解题思路

1. 字符权值分配：

   • 遍历字符串，记录每个字符首次出现的位置，按顺序分配权值（从 $0$ 到 $nc-1$）。
   • 例如，字符串 "abac" 的字符权值为 a:0, b:1, c:2，$nc=3$。

2. 计算哈希值：

   • 将字符串视为一个 $nc$ 进制的数，每个字符的权值作为该位的数字。
   • 哈希值计算公式为： [ hash = \sum_{i=0}^{n-1} (val(s[i]) \times nc^{n-1-i}) \mod MOD ] 其中 $val(s[i])$ 是字符 $s[i]$ 的权值，$MOD$ 是一个大质数（如 $10^9+7$）。

3. 哈希表存储：

   • 使用哈希表（如 unordered_map）存储计算出的哈希值，避免重复计算。

关键优化

• 避免大数溢出：
  • 在计算过程中每一步都取模，防止数值溢出。
• 预处理幂次：
  • 预处理 $nc$ 的幂次数组 $pow[i] = nc^i \mod MOD$，加速计算。

复杂度分析

• 时间复杂度：
  • 遍历字符串计算权值：$O(n)$。
  • 计算哈希值：$O(n)$。
• 空间复杂度：
  • 存储字符权值和幂次数组：$O(n + nc)$。

代码实现

#include<iostream>
#include<string>
#include<cstdio>

using namespace std;

const int q=10000007;

string str;
int h[q];
int b[500];

int main()
{
    int t,e,n,nc,k=0,ans=0;
    scanf("%d%d",&n,&nc);
    cin>>str;
    for (int i=0;i<str.length();i++)
    {
         if (b[str[i]]==0) b[str[i]]=++k;
         if (k==nc) break;
    }
    for (int i=0;i<str.length()-n+1;i++)
    {
         t=0;
         for (int j=i;j<i+n;j++)
            t=(t*nc+b[str[j]])% q;
         if (h[t]==0) 
         {
             h[t]=1;
             ans++;
         }
    }
    printf("%d",ans);
    return(0);
}