https://codeforces.com/contest/985/problem/F
题目大意
给出字符串 $n \ (n \le 2 \times 10^5)$ 长的字符串 $S$，和 $m \ *(m \le 2 \times 10^5)$ 个询问。
定义串 $S$ 和 $T$ 是 isomorphic 的，当且仅当，$S$ 和 $T$ 的字符集之间能建立一一映射，使得 $S$ 和 $T$ 可以通过这组一一映射互相转化。
每组询问给出 $i, j, len$，问对于两个 $S$ 的子串 $S[i, i + len - 1]$ 与 $S[j, j + len - 1]$ 是不是 isomorphic 的。
简要题解
观察
- 注意到对于 isomorphic 的一对串，我们其实并不关注具体的字符是什么，我们关注的其实是每种字母的下标的集合。如果两个串对应的“每组字母下标集合”的集合满足一一映射，则其实它们是 isomorphic 的。
- 实际上我们只要关注 $S[i, i + len - 1]$ 中每个字母第一次出现的位置，看其对应的字符是什么，我们就知道，如果成立，那么字符的一一对应关系是怎样的。
有了以上的观察，我们可以处理 $26$ 个 $01$ 串，每个串只关注某个字母 $c$（原串如果是 $c$ 字母则新串为 $1$ 其他字母时为 $0$）。这样对于 $S[i, i + len - 1]$ 与 $S[j, j + len - 1]$ 由观察 2 可以知道每一组映射，我们检查对应的 $01$ 串是否匹配即可。
后缀数组因为多个 $log$ 所以被卡了。。。ST 表也不能复杂度更低，且会爆空间。
void solve() {
int n, q; cin >> n >> q;
string s; cin >> s;
vector<vector<array<int, 3>>> qs(n);
int x, y, len;
for (int i = 0; i < q; i++) {
cin >> x >> y >> len;
x--; y--;
qs[x].push_back({y, len, i});
}
vector<int> ss(n * 26);
for (int i = 0; i < 26; i++) {
for (int j = 0; j < n; j++) {
if (s[j] - 'a' == i) ss[i * n + j] = 1;
}
}
SA sa(ss);
SegT segt(sa.lc);
auto lcp = [&](int i, int j) -> int {
// cerr << i << ' ' << j << ' ' << 26 * n - i << endl;
if (i == j) return 26 * n - i;
int a = sa.rk[i], b = sa.rk[j];
if (a > b) swap(a, b);
b--;
return segt.query(a, b);
};
vector<int> ans(q, 1);
vector<int> nxt(26, n);
for (int i = n - 1; i >= 0; i--) {
nxt[s[i] - 'a'] = i;
for (auto [j, len, qid] : qs[i]) {
for (int c = 0; c < 26; c++) {
if (nxt[c] > i + len - 1) {
continue;
}
int cj = s[j + (nxt[c] - i)] - 'a';
if (lcp(c * n + i, cj * n + j) < len) {
ans[qid] = 0;
break;
}
}
}
}
for (int i : ans) {
cout << (i ? "YES" : "NO") << '\n';
}
}
最后只好写双哈。
复杂度
$T$：$O((n + q)\Sigma)$
$S$：$O((n + q)\Sigma)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int D = 2;
struct Hash {
using ULL = unsigned long long;
static constexpr int MODS_LEN = 10;
static array<ULL, MODS_LEN> MODS;
static void genMod(int st = 1e9) {
int p = 0;
for (ULL i = st; p < MODS_LEN; i++) {
int f = 1;
for (ULL j = 2; j * j <= i; j++) {
if (i % j == 0) { f = 0; break; }
}
if (f) MODS[p++] = i;
}
// for (auto i : MODS) cerr << i << ", ";
// cerr << endl;
}
static mt19937_64 mt;
static ULL rndi(ULL l, ULL r) { return mt() % (r - l + 1) + l; }
static array<ULL, D> md;
static vector<array<ULL, D>> pw, ipw;
static ULL qp(ULL x, ULL n, ULL m) {
ULL ans = 1;
while (n) {
if (n & 1) ans = ans * x % m;
x = x * x % m;
n >>= 1;
}
return ans;
}
static void init(int n) {
vector<int> vis(MODS_LEN);
for (int i = 0; i < D; i++) {
int j = rndi(1, MODS_LEN - D);
for (int k = 0; k < MODS_LEN; k++) {
if (vis[k]) continue;
if (!--j) {
vis[k] = 1;
md[i] = MODS[k];
break;
}
}
}
pw.resize(n + 1);
ipw.resize(n + 1);
for (int i = 0; i < D; i++) {
ULL b = rndi(500, 1000) * 2 + 1, ib = qp(b, md[i] - 2, md[i]);
pw[0][i] = ipw[0][i] = 1;
for (int j = 1; j <= n; j++) {
pw[j][i] = pw[j - 1][i] * b % md[i];
ipw[j][i] = ipw[j - 1][i] * ib % md[i];
}
}
}
int n;
vector<array<ULL, D>> h;
Hash(vector<char> s, bool need_init = true) : n(s.size()), h(n + 1) {
static_assert(D <= MODS_LEN);
if (need_init) init(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < D; j++) {
h[i + 1][j] = (h[i][j] + pw[i][j] * s[i]) % md[j];
}
}
}
array<ULL, D> query(int l, int r) {
array<ULL, D> ans;
for (int i = 0; i < D; i++) {
ans[i] = ipw[l][i] * (h[r + 1][i] - h[l][i] + md[i]) % md[i];
}
return ans;
}
};
array<Hash::ULL, Hash::MODS_LEN> Hash::MODS = {1000000007, 1000000009,
1000000021, 1000000033, 1000000087, 1000000093, 1000000097, 1000000103,
1000000123, 1000000181,};
#ifdef OTTFF
mt19937_64 Hash::mt(42);
#else
mt19937_64 Hash::mt(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
array<Hash::ULL, D> Hash::md;
vector<array<Hash::ULL, D>> Hash::pw;
vector<array<Hash::ULL, D>> Hash::ipw;
void solve() {
int n, q; cin >> n >> q;
string s; cin >> s;
vector<vector<array<int, 3>>> qs(n);
int x, y, len;
for (int i = 0; i < q; i++) {
cin >> x >> y >> len;
x--; y--;
qs[x].push_back({y, len, i});
}
vector<char> ss(n * 26);
for (int i = 0; i < 26; i++) {
for (int j = 0; j < n; j++) {
if (s[j] - 'a' == i) ss[i * n + j] = 1;
}
}
Hash hsh(ss);
auto check = [&](int ci, int i, int cj, int j, int len) {
int li = ci * n + i, ri = li + len - 1;
int lj = cj * n + j, rj = lj + len - 1;
return hsh.query(li, ri) == hsh.query(lj, rj);
};
vector<int> ans(q, 1);
vector<int> nxt(26, n);
for (int i = n - 1; i >= 0; i--) {
nxt[s[i] - 'a'] = i;
for (auto [j, len, qid] : qs[i]) {
for (int c = 0; c < 26; c++) {
if (nxt[c] > i + len - 1) {
continue;
}
int cj = s[j + (nxt[c] - i)] - 'a';
if (!check(c, i, cj, j, len)) {
ans[qid] = 0;
break;
}
}
}
}
for (int i : ans) {
cout << (i ? "YES" : "NO") << '\n';
}
}
int main() {
// Hash::genMod();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] E. Triangle Tree - Codeforces Round 1000 (Div. 2)