本文主要是介绍BJ模拟（2） D3T2 相似子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！ 相似子串 题目背景： 分析：这道题的暴力直到现在都还在RE我想我可能是智障吧，当时把暴力交上去后，刷了3屏的提交记录，我也很绝望啊·····但是知道现在都还是挂掉了······虽然正解已经调过了，但是心情还是非常的不好······考虑处理的方法，首先如果把字符串拷贝下来再进行比较，那显然时间会爆炸，那么我们考虑有什么快一点的方法，那当然就是hash啦，但是如果直接整串hash，我们该如何判断相似呢，考虑到这道题的数据范围，我们可以考虑直接对串hash26次，从而得到26个01串，然后将两串的每一个字母的hash进行比对，如果最后没有差别那就说明相等，如果有两处区别，并且两处分别为正负Gi次方，（G为hash底数），说明相似，其他情况均说明两串不相似，代码写起来有点麻烦，调了很久，最后发现有一个小错，和正解拍了几千组都没有拍出问题····· Source： #include #include #include #include #include #include #include #include #include #include using namespace std; const int G = 3; const int MAXN = 100000 + 10; int n, x, y, ind; int pos[MAXN], father[MAXN]; char z; unsigned long long h1[30][MAXN], h2[30][MAXN], hash_pow[MAXN], v[MAXN]; struct node { int to, w; node(int to, int w) : to(to), w(w) {} node() {} }; vector edge[MAXN]; map m; struct Tree { int dep, size; int son, father, top; int num, w; } tree[MAXN]; template inline void R(T &x) { static bool iosig; static char c; for (c = getchar(), iosig = false; !isdigit(c); c = getchar()) if (c == '-') iosig = true; for (x = 0; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ '0'); if (iosig) x = -x; } const int OUT_LEN = 1024 * 1024; char obuf[OUT_LEN], *oh = obuf; inline void write_char(char c) { if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdin), oh = obuf; *oh++ = c; } inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); } inline void write(bool type) { if (type) write_char('Y'), write_char('E'), write_char('S'), write_char('\n'); else write_char('N'), write_char('O'), write_char('\n'); } inline void add_edge(int x, int y, int z) { edge[x].push_back(node(y, z)); edge[y].push_back(node(x, z)); } inline void readin() { R(n); for (int i = 1; i < n; ++i) { R(x), R(y), scanf("%c", &z); add_edge(x, y, z - 'a' + 1); } } inline void dfs1(int cur, int fa, int w) { tree[cur].dep = tree[fa].dep + 1; tree[cur].size = 1; tree[cur].w = w; tree[cur].father = fa; for (int p = 0; p < edge[cur].size(); ++p) if (edge[cur][p].to != fa) { dfs1(edge[cur][p].to, cur, edge[cur][p].w); tree[cur].size += tree[edge[cur][p].to].size; if (!tree[cur].son || tree[edge[cur][p].to].size > tree[tree[cur].son].size) tree[cur].son = edge[cur][p].to; } } inline void dfs2(int cur, int top) { tree[cur].top = top; tree[cur].num = ++ind; pos[ind] = cur, v[ind] = tree[cur].w; if (tree[cur].son) dfs2(tree[cur].son, top); for (int p = 0; p < edge[cur].size(); ++p) if (!tree[edge[cur][p].to].num) dfs2(edge[cur][p].to, edge[cur][p].to); } inline unsigned long long get_hash_up(int pos, int l, int r) { return h1[pos][r] - hash_pow[r - l + 1] * h1[pos][l - 1]; } inline unsigned long long get_hash_down(int pos, int l, int r) { return h2[pos][l] - hash_pow[r - l + 1] * h2[pos][r + 1]; } inline int get_lca(int u, int v) { while (tree[u].top != tree[v].top) { int x = tree[u].top, y = tree[v].top; if (tree[x].dep > tree[y].dep) u = tree[x].father; else v = tree[y].father; } return tree[u].dep < tree[v].dep ? u : v; } inline int get_length(int u, int v) { int p = u, q = v; while (tree[u].top != tree[v].top) { int x = tree[u].top, y = tree[v].top; if (tree[x].dep > tree[y].dep) u = tree[x].father; else v = tree[y].father; } if (tree[u].dep > tree[v].dep) return tree[p].dep + tree[q].dep - 2 * tree[v].dep; else return tree[p].dep + tree[q].dep - 2 * tree[u].dep; } inline unsigned long long get_hash(int pos, int u, int v) { unsigned long long s_up = 0, s_down = 0; int lca = get_lca(u, v); unsigned long long temp1 = 1, temp2 = hash_pow[tree[u].dep - tree[lca].dep]; while (tree[u].top != tree[lca].top) { int x = tree[u].top; s_up += temp1 * get_hash_up(pos, tree[x].num, tree[u].num); temp1 *= hash_pow[tree[u].num - tree[x].num + 1]; u = tree[x].father; } if (u != lca) s_up += temp1 * get_hash_up(pos, tree[tree[lca].son].num, tree[u].num); while (tree[v].top != tree[lca].top) { int y = tree[v].top; s_down = s_down * hash_pow[tree[v].num - tree[y].num + 1] + get_hash_down(pos, tree[y].num, tree[v].num); v = tree[y].father; } if (v != lca) s_down = s_down * hash_pow[tree[v].dep - tree[lca].dep] + get_hash_down(pos, tree[tree[lca].son].num, tree[v].num); return s_up + temp2 * s_down; } inline int get_father(int x) { return (father[x] == x) ? x : (father[x] = get_father(father[x])); } inline void unite(int x, int y) { int fa1 = get_father(x), fa2 = get_father(y); if (fa1 != fa2) father[fa1] = fa2; } inline bool solve_query() { int k, u1, v1, u2, v2, len1, len2, len, fa, cnt = 0; static unsigned long long hash1[30], hash2[30]; static int temp[30]; R(k), R(u1), R(v1), R(u2), R(v2); len1 = get_length(u1, v1), len2 = get_length(u2, v2); for (int i = 1; i <= 26; ++i) hash1[i] = G * get_hash(i, u1, v1), hash2[i] = G * get_hash(i, u2, v2); for (int i = 1; i <= 26; ++i) father[i] = i; while (k--) { char c1 = 0, c2 = 0; while (c1 < 'a' || c1 > 'z') c1 = getchar(); while (c2 < 'a' || c2 > 'z') c2 = getchar(); unite(c1 - 'a' + 1, c2 - 'a' + 1); } for (int i = 1; i <= 26; ++i) if ((fa = get_father(i)) != i) hash1[fa] += hash1[i], hash2[fa] += hash2[i]; if (len1 != len2) return false; else len = len1; for (int i = 1; i <= 26; ++i) if (get_father(i) == i) { unsigned long long hash = hash1[i] - hash2[i]; if (m.count(hash)) temp[i] = m[hash], cnt++; else if (!hash) temp[i] = 0; else return false; } else temp[i] = 0; if (!cnt) return true; if (cnt != 2) return false; cnt = 0; for (int i = 1; i <= 26; ++i) { cnt += temp[i]; if (abs(cnt) > len) return false; } return cnt ? false : true; } int q; inline void pre() { R(q), hash_pow[0] = 1; for (int i = 1; i < MAXN; ++i) { hash_pow[i] = hash_pow[i - 1] * G; if (!m.count(hash_pow[i])) m[hash_pow[i]] = i; if (!m.count(-hash_pow[i])) m[-hash_pow[i]] = -i; } for (int i = 1; i <= 26; ++i) for (int j = 1; j <= n; ++j) h1[i][j] = h1[i][j - 1] * G + (v[j] == i ? 1 : 0); for (int i = 1; i <= 26; ++i) for (int j = n; j >= 1; --j) h2[i][j] = h2[i][j + 1] * G + (v[j] == i ? 1 : 0); } inline void solve() { readin(); dfs1(1, 1, 0); dfs2(1, 1); pre(); while (q--) solve_query() ? write(true) : write(false); flush(); } int main() { solve(); return 0; } 这篇关于BJ模拟（2） D3T2 相似子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
