正反哈希两种版子

1：这种版子开的二维数组更合理，用于单个字符串的最大长度，未知的情况，但是第二维大小只为2，故可以满足大部分情况

#define int unsigned long long
int n;
int p[N];
int h[N][2];
int l[N], r[N];
int get1(int l, int r)
{
    return h[r][0] - h[l - 1][0] * p[r - l + 1];
}
int get2(int l, int r)
{
    return h[r][1] - h[l - 1][1] * p[r - l + 1];
}

void solve()
{
    p[0] = 1;
    for (int i = 1; i <= N; i++)
        p[i] = p[i - 1] * P;

    cin >> n;
    vector<string> s(n + 1);
    string S = " ";
    
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        l[i] = r[i - 1] + 1;
        r[i] = l[i] + s[i].size() - 1;
        S += s[i];
    }

    int len = S.size() - 1;
    h[0][0] = 0;

    for (int i = 1; i <= len; i++)
    {
        h[i][0] = h[i - 1][0] * P + S[i];
    }

    reverse(S.begin(), S.end());
    S = " " + S;
    h[0][1] = 0;

    for (int i = 1; i <= len; i++)
    {
        h[i][1] = h[i - 1][1] * P + S[i];
    }

    int ans = 0;
    auto check = [&](int a, int b, int c) -> bool
    {
        int aa = s[a].size();
        int bb = s[b].size();
        int cc = s[c].size();
    
        if (get1(l[a], r[a]) * p[bb + cc] + get1(l[b], r[b]) * p[cc] + get1(l[c], r[c]) == get2(len - r[a] + 1, len - l[a] + 1) + get2(len - r[b] + 1, len - l[b] + 1) * p[aa] + get2(len - r[c] + 1, len - l[c] + 1) * p[bb + aa])
            return true;
        return false;
    };
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i - 1; j++)
        {
            for (int k = i + 1; k <= n; k++)
                if (check(j, i, k))
                {
                    ans++;
                }
        }
    }

    cout << ans << endl;
}

2：这种版子开的二维数组，用于单个字符串的最大长度和字符串个数已经知道的情况，或者未知但都有一个限制，不然不好开二维数组的大小，时间效率不知道为什么比上面的要慢，不应该都是o(N)级别的吗

int n;
char s[M][20000];
int p[N];
int hash1[M][20000], hash2[M][2000];
int get1(int l, int r, int x)
{
    return hash1[x][r] - hash1[x][l - 1] * p[r - l + 1];
}
int get2(int l, int r, int x)
{
    return hash2[x][l] - hash2[x][r + 1] * p[r - l + 1];
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i] + 1;

    p[0] = 1;
    for (int i = 1; i <= N; i++)
        p[i] = p[i - 1] * P;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= strlen(s[i] + 1); j++)
        {
            hash1[i][j] = hash1[i][j - 1] * P + s[i][j];
        }
        for (int j = strlen(s[i] + 1); j >= 1; j--)
        {
            hash2[i][j] = hash2[i][j + 1] * P + s[i][j];
            // cout << hash2[i][j] << ' ';
        }
        // cout << endl;
        // cout << get1(1, strlen(s[i] + 1), i) << " " << get2(1, strlen(s[i] + 1), i) << endl;
    }

    int ans = 0;
    auto check = [&](int a, int b, int c) -> bool
    {
        int aa = strlen(s[a] + 1);
        int bb = strlen(s[b] + 1);
        int cc = strlen(s[c] + 1);

        if (get1(1, aa, a) * p[bb + cc] + get1(1, bb, b) * p[cc] + get1(1, cc, c) == get2(1, aa, a) + get2(1, bb, b) * p[aa] + get2(1, cc, c) * p[aa + bb])
            return 1;
        return 0;
    };