毎日1題のテンセントのアルゴリズムの筆の試験問題(文字列Hash)

####与えられたA、Bの2つの文字列を記述し、以下の規則を定義する

は、各Aの長いkの異なるサブストリングについて、統計的サブストリングがBに現れる回数

である.

AおよびBの文字列係数は、すべての出現回数の和である.A="abab"B="abababab"k=2のように、Aの長さが2の異なるサブ列はabとbaであり、この2つの列がbに現れる回数の和は5

である.
####構想文字列Hashの黒魔法、詳しく紹介https://blog.csdn.net/pengwill97/article/details/80879387

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

typedef long long llint;

const llint MOD = 0xdeadbeefdead; //244837814099629
const int KK = 293;

int k;
string A, B;
map<llint, int> mpa, mpb;

void calc(const string& s, map<llint, int>& mp) {
    llint h = 0;
    const int n = s.size();
    llint u = 1;
    for (int i = 0; i < n && i < k; i++) {
        h = ((h * KK) % MOD + s[i]) % MOD;
    }

    for (int i = 0; i < k - 1; i++) {
        u = (u * KK) % MOD;
    }

    mp[h]++;

    for (int i = k; i < n; i++) {
        h = ((h - u * s[i - k] % MOD) % MOD + MOD) % MOD;
        h = ((h * KK) % MOD + s[i]) % MOD;

        mp[h]++;
    }

}

int main() {

    input(k >> A >> B);

    calc(A, mpa);
    calc(B, mpb);

    llint ans = 0;
    for (const auto& p: mpa) {
        ans += mpb[p.first];
    }
    print(ans);

    return 0;
}