用c++写一个字符串哈希的模板代码

以下是一个基本的字符串哈希模板代码（使用了多项式Hash算法）：

#include <stdio.h>
#include <string.h>

#define MAXN 1000010  // 最大字符串长度
#define P 31          // 素数P，用于哈希计算
#define MOD 1000000009 // 哈希计算结果取模值

typedef long long ll;

char s[MAXN];
ll h[MAXN], p[MAXN];

// 初始化哈希相关数组
void init()
{
    p[0] = 1;
    for (int i = 1; i < MAXN; i++)
    {
        p[i] = p[i - 1] * P % MOD;
    }
}

// 计算字符串s的哈希值
void hash()
{
    int n = strlen(s);
    h[0] = s[0] - 'a' + 1; // 初始化第一个字符的哈希值

    // 依次计算每个字符的哈希值
    for (int i = 1; i < n; i++)
    {
        h[i] = (h[i - 1] * P + s[i] - 'a' + 1) % MOD;
    }
}

// 计算子串[l, r]的哈希值
ll get_hash(int l, int r)
{
    if (l == 0)
    {
        return h[r];
    }
    return (h[r] - h[l - 1] * p[r - l + 1] % MOD + MOD) % MOD;
}

int main()
{
    init();
    scanf("%s", s);
    hash();
    int n = strlen(s);

    // 输出每个后缀的哈希值
    for (int i = 0; i < n; i++)
    {
        printf("%lld ", get_hash(i, n - 1));
    }

    return 0;
}

这个模板代码可以用于计算一个字符串中每个后缀的哈希值。在使用时，可以根据需要修改哈希算法和哈希计算结果的取模值。