lc336 回文对

给定字符串数组words[n]，寻找二元组(i,j)满足0<=i,j<n，并且i!=j，而且words[i]+words[j]是回文串，求满足条件的二元组的个数。
1<=n<=5000; 0<=words[i].length<=300; words[i]由小写英文字母组成。

判断回文可以检查正序和逆序的哈希值是否相等来判断；在知道两字符串的长度和哈希的前提下，可以O(1)算出将它们连起来的字符串的哈希值。

using ll = long long;
using hval = pair<ll,ll>;
const ll b1 = 433, m1 = 1000000433;
const ll b2 = 439, m2 = 1000000439;
ll p1[305], p2[305];

int initialize = [](){
	p1[0] = p2[0] = 1;
	for (int i = 1; i <= 300; i++) {
		p1[i] = p1[i-1] * b1 % m1;
        p2[i] = p2[i-1] * b2 % m2;
	}
    return 0;
}();

hval get1(string &s) {
    ll hx = 0, hy = 0;
	int ns = s.size();
	for (int i = 0; i < ns; i++) {
		hx = hx * b1 + s[i]-'a'; hx %= m1;
        hy = hy * b2 + s[i]-'a'; hy %= m2;
	}
    return {hx,hy};
}

hval get2(string &s) {
    ll hx = 0, hy = 0;
	int ns = s.size();
	for (int i = ns-1; i >= 0; i--) {
		hx = hx * b1 + s[i]-'a'; hx %= m1;
        hy = hy * b2 + s[i]-'a'; hy %= m2;
	}
    return {hx,hy};
}

hval concat(int na, hval &a, int nb, hval &b) {
    ll hx = 0, hy = 0;
    auto &[ax,ay] = a;
    auto &[bx,by] = b;
	hx = ax * p1[nb] + bx; hx %= m1;
    hy = ay * p2[nb] + by; hy %= m2;
    return {hx,hy};
}

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
		int n = words.size();
		vector<hval> pre(n), suf(n);
		for (int i = 0; i < n; i++) {
			pre[i] = get1(words[i]);
			suf[i] = get2(words[i]);
		}
		
		vector<vector<int>> ans;
        hval u, v;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) if (i!=j) {
                u = concat(words[i].size(),pre[i],words[j].size(),pre[j]);
                v = concat(words[j].size(),suf[j],words[i].size(),suf[i]);
                if (u == v) {
                    ans.push_back({i,j});
                }
			}
		}
		return ans;
    }
};