c++利用哈希算法写一个判断一个字符串是否是另一个字符串的子串

可以使用哈希算法来判断一个字符串是否是另一个字符串的子串。首先，对于目标字符串和子串，分别计算它们的哈希值。然后，遍历目标字符串，依次计算每个长度为子串长度的子串的哈希值，与子串的哈希值进行比较。如果相等，则说明目标字符串中存在该子串。如果不相等，则继续遍历。

相关问题

字符串哈希算法c++

字符串哈希算法是一种将字符串映射为数字的算法，常用于字符串的比较和匹配。在C++中，可以使用字符串哈希算法来加速字符串的比较操作。

引用\[1\]中的代码示例展示了一个使用字符串哈希算法的C++代码。该代码使用了前缀和数组和字符串数组来存储字符串，并通过计算哈希值来比较两个子串是否相等。其中，哈希值的计算使用了前缀和数组和幂运算。

引用\[2\]中的解释指出，使用字符串哈希的目的是为了比较字符串时不直接比较字符串本身，而是比较它们对应映射的数字。这样可以将子串的哈希值的时间复杂度降低到O(1)，从而节省时间。

引用\[3\]中的代码示例也展示了一个使用字符串哈希算法的C++代码。该代码使用了前缀和数组和字符串数组来存储字符串，并通过计算哈希值来比较两个子串是否相等。与引用\[1\]中的代码类似，哈希值的计算也使用了前缀和数组和幂运算。

综上所述，字符串哈希算法是一种将字符串映射为数字的算法，常用于字符串的比较和匹配。在C++中，可以使用前缀和数组和幂运算来计算字符串的哈希值，并通过比较哈希值来判断两个子串是否相等。
#### 引用[.reference_title]
- *1* [C++算法题 # 33 字符串哈希](https://blog.csdn.net/weixin_44536804/article/details/123425533)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insertT0,239^v3^insert_chatgpt"}} ] [.reference_item]
- *2* [字符串哈希(c++)](https://blog.csdn.net/qq_41829492/article/details/120980055)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insertT0,239^v3^insert_chatgpt"}} ] [.reference_item]
- *3* [AcWing 841. 字符串哈希（C++算法）](https://blog.csdn.net/YSA__/article/details/108453403)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insertT0,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]

用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;
}

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