サブストリング判定アルゴリズム(KMP&文字列ハッシュ)

タイトルの説明
与えられた文字列haystackおよびneedleは、needleがhaystackのサブストリングであるか否かを判定する.以下に示す2つのアルゴリズムの複雑さはいずれもO(m)である.転送ゲート:Leetcode 28
KMPアルゴリズムneedleのnext が最初に計算され、その後、KMPアルゴリズムが実行される.

class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        if (needle.empty())
            return 0;

        int m = haystack.size();
        int n = needle.size();

        // 'next' array of needle
        vector<int> next(n);
        next[0] = -1;

        int j = -1;
        for (int i = 1; i < n; ++i)
        {
            while (j != -1 && needle[i] != needle[j + 1])
                j = next[j];
            if (needle[i] == needle[j + 1])
                ++j;
            next[i] = j;
        }

        // kmp algorithm
        j = -1;
        for (int i = 0; i < m; ++i)
        {
            while (j != -1 && haystack[i] != needle[j + 1])
                j = next[j];
            if (haystack[i] == needle[j + 1])
                ++j;

            if (j == n - 1)
                return i - n + 1;
        }

        return -1;
    }
};

文字列ハッシュアルゴリズム
ハッシュ値=26進文字列

class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        const long long mod = 10e9 + 7;
        int m = haystack.length();
        int n = needle.length();

        if (m < n) return -1;

        long long h_hash = 0;
        long long n_hash = 0;

        long long pow = 1;              //   26^n
        
        //           
        for (int i = 0; i < n; ++i)
        {
            pow = (pow * 26) % mod;
            h_hash = (h_hash * 26 + haystack[i] - 'a') % mod;
            n_hash = (n_hash * 26 + needle[i] - 'a') % mod;
        }

        if(h_hash == n_hash) return 0;

        //     ，       
        for (int l = 0, r = n; r < m; ++l, ++r)
        {
            h_hash = (h_hash * 26 - pow * (haystack[l] - 'a') + haystack[r] - 'a') % mod;
            if(h_hash == n_hash) return l + 1;
        }

        return -1;
    }
};