【字符串】后缀自动机

【字符串】后缀自动机 - 模板

本文主要是介绍【字符串】后缀自动机 - 模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解决字符串中子串的相关问题

/*******************后缀自动机SAM***********************
- 总点数tot，点的index属于[1-tot]，空串/根为1
- last为上一次插入的点
- fa为点的parent树父节点 / 最长 出现位置与自己不同 的后缀
- ch[n][s] 指节点n末尾加字符s所转移到的点
- len指该节点的串的 最长长度，注意到 最短长度 等于 len[fa[n]] + 1 即父节点最长 + 1
- endpos[n] 参考get_endpos()的注释
*/struct SAM
{static const int MAXN = 1e6 + 10, MAXS = 27;int tot = 1, last = 1, fa[MAXN << 1], ch[MAXN << 1][MAXS], len[MAXN << 1], endpos[MAXN << 1];void clear(){for (int i = 0; i <= tot; i++){fa[i] = len[i] = endpos[i] = 0;for (int k = 0; k < MAXS; k++)ch[i][k] = 0;}tot = 1;last = 1;}// 延长一个字符，注意输入的是转换后的数字void extend(int w){int p = ++tot, x = last, r, q;endpos[p] = 1;for (len[last = p] = len[x] + 1; x && !ch[x][w]; x = fa[x])ch[x][w] = p;if (!x)fa[p] = 1;else if (len[x] + 1 == len[q = ch[x][w]])fa[p] = q;else{fa[r = ++tot] = fa[q];memcpy(ch[r], ch[q], sizeof ch[r]);len[r] = len[x] + 1;fa[p] = fa[q] = r;for (; x && ch[x][w] == q; x = fa[x])ch[x][w] = r;}}//*注意vector占用的空间vector<int> p[MAXN << 1]; // 建立parent树，以便从上到下dfsvoid dfs(int u){int v;for (int i = 0; i < p[u].size(); i++){v = p[u][i];dfs(v);endpos[u] += endpos[v];}}// 注意: 在使用该方法前，endpos[]代表每个点作为“终结点”的次数// 使用该方法后，endpos[]指在串中出现总次数，即原数组的子树求和void get_endpos(){for (int i = 1; i <= tot; i++)p[i].clear();for (int i = 2; i <= tot; i++){p[fa[i]].push_back(i); // 建立parent树，以便从上到下dfs}dfs(1);for (int i = 1; i <= tot; i++)p[i].clear();}//* 确认是否有抄写错误时使用该方法//* 必须在输入任何数据前自检，此前的数据会被清空static const int STC = 998244353;void self_test(){clear();for (int i = 1; i <= 1000; i++)extend(i * i % 26 + 1);int tmp = 107 * last + 301 * tot;for (int i = 1; i <= tot; i++){tmp = (tmp * 33 + fa[i] * 101 + len[i] * 97) % STC;for (int k = 1; k < MAXS; k++)tmp = (tmp + k * ch[i][k]) % STC;}assert("stage 1" && tmp == 393281314); // stage1 : 检查建树是否正确tmp = 0;get_endpos();for (int i = 1; i <= tot; i++)tmp = (tmp * 33 + endpos[i]) % STC;assert("stage 2" && tmp == 178417668); // stage2 : 检查endpos计算是否正确，如果您修改了endpos[]的含义则会报错cout << "Self Test Passed.Remember to delete this function's use." << endl;clear();}// 调试时调用void debug_print(){cout << '\n';for (int i = 1; i <= tot; i++){cout << "node:" << i << " father:" << fa[i] << " endpos:" << endpos[i] << " len:" << len[i] << '\n';}}void solve(){// 这里输入解题逻辑// - 建树string s; cin >> s;clear();for (auto t : s) extend(t - 'a');// - get_endpos()get_endpos();// - 求解}
} sam;// *************************************************