模板

字符串哈希

const int maxl = 100005;
const int mod1 = 1000000007;
const int base1 = 131;
const int mod2 = 998244353;
const int base2 = 233;
int powbase1[maxl] , powbase2[maxl];
void init(){powbase1[0] = 1;fo(i , 1 , maxl - 5)powbase1[i] = 1ll * powbase1[i - 1] * base1 % mod1;powbase2[0] = 1;fo(i , 1 , maxl - 5)powbase2[i] = 1ll * powbase2[i - 1] * base2 % mod2;
}
struct mystring{string s;int len;pair<int , int> hsh[maxl];void read(){cin >> s;len = s.size();s = " " + s;fo(i , 1 , len){hsh[i].first = (1ll * hsh[i - 1].first * base1 % mod1 + s[i]) % mod1;hsh[i].second = (1ll * hsh[i - 1].second * base2 % mod2 + s[i]) % mod2;}}pair<int , int> gethash(int l , int r){int ans1 = hsh[r].first;int tmp1 = 1ll * hsh[l - 1].first * powbase1[r - l + 1] % mod1;ans1 = (ans1 - tmp1 + mod1) % mod1;int ans2 = hsh[r].second;int tmp2 = 1ll * hsh[l - 1].second * powbase2[r - l + 1] % mod2;ans2 = (ans2 - tmp2 + mod2) % mod2;return mp(ans1 , ans2);}pair<int , int> gethash(){return hsh[len];}
};

其他小trick

创建n行m列的矩阵

vector<vector<int>> dp(n + 5 , vector<int>(m + 5 , 0));