【C++】字符串|子串类问题模板
这一篇文章主要是一些与某一字符串的子串有关问题的算法模板。
Manacher
是一种可以在 O(n) 的时间复杂度内计算出给定字符串的最长回文子串长度的算法。
主要思想和扩展KMP（Z函数）几乎一致，均利用一个盒子加速计算过程。
题目：P3805 【模板】Manacher（https://www.luogu.com.cn/problem/P3805）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
vector<char> str;
str.emplace_back('#');
str.emplace_back('%');
for (auto& i : s)
{
str.emplace_back(i);
str.emplace_back('%');
}
vector<int> d(str.size());
d[1] = 1;
for (int i = 2, l = 0, r = 0; i < str.size(); i++)
{
if (i <= r) d[i] = min(d[r - i + l], r - i + 1);
while (i + d[i] < str.size() && str[i - d[i]] == str[i + d[i]]) d[i]++;
if (i + d[i] - 1 > r) l = i - d[i] + 1, r = i + d[i] - 1;
}
int res = 0;
for (auto& i : d) res = max(res, i - 1);
cout << res << endl;
return 0;
}
后缀自动机 (SAM)
介绍：简单来说就是把字符串的所有子串以图的形式压缩存储（很像Trie）。利用构建的后缀自动机（是一个DAG图）和其连接边抽离得到的后缀连接树可以解决许多字符串子串问题。
不同子串个数
即求原串有多少个子串，这里指的是本质不同子串数量（也就是位置不同的算一个）
有两种方法：
1.利用后缀自动机每条边都代表一个子串，dp求边数即可。
2.利用后缀树的性质，每个节点代表的子串个数=节点最长子串长度-父亲节点最长子串长度。（这个比法1快）
题目：P2408 不同子串个数（https://www.luogu.com.cn/problem/P2408）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
using ll = long long;
struct SAM
{
vector<vector<int>> edg, ch;
vector<ll> fa, len, cnt;
int pid = 1, np = 1;
SAM(int size)
{
int est = size * 2 + 5;
ch.resize(est, vector<int>(26));
cnt.resize(est, 0);
len.resize(est, 0);
fa.resize(est, 0);
}
// 建立后缀自动机
void extend(int c)
{
c -= 'a';
int p = np;
np = ++pid;
len[np] = len[p] + 1;
cnt[np] = 1;
while (p && !ch[p][c])
{
ch[p][c] = np;
p = fa[p];
}
if (p == 0) fa[np] = 1;
else
{
int q = ch[p][c];
if (len[q] == len[p] + 1) fa[np] = q;
else
{
int nq = ++pid;
len[nq] = len[p] + 1;
fa[nq] = fa[q];
fa[q] = nq;
fa[np] = nq;
while (p && ch[p][c] == q)
{
ch[p][c] = nq;
p = fa[p];
}
ch[nq] = ch[q];
}
}
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string s;
int n;
cin >> n >> s;
SAM sam(s.size());
for (auto& i : s) sam.extend(i);
ll res = 0;
for (int i = 2; i <= sam.pid; i++)
{
res += sam.len[i] - sam.len[sam.fa[i]];
}
cout << res << endl;
return 0;
}每个子串的出现个数
利用抽离出后缀连接树，在树上做dfs，对cnt求和即可。
题目：P3804 【模板】后缀自动机（SAM）（https://www.luogu.com.cn/problem/P3804）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
using ll = long long;
struct SAM
{
vector<vector<int>> edg, ch;
vector<ll> fa, len, cnt;
int pid = 1, np = 1;
SAM(int size)
{
int est = size * 2 + 5;
ch.resize(est, vector<int>(26));
cnt.resize(est, 0);
len.resize(est, 0);
fa.resize(est, 0);
}
// 建立后缀自动机
void extend(int c)
{
c -= 'a';
int p = np;
np = ++pid;
len[np] = len[p] + 1;
cnt[np] = 1;
while (p && !ch[p][c])
{
ch[p][c] = np;
p = fa[p];
}
if (p == 0) fa[np] = 1;
else
{
int q = ch[p][c];
if (len[q] == len[p] + 1) fa[np] = q;
else
{
int nq = ++pid;
len[nq] = len[p] + 1;
fa[nq] = fa[q];
fa[q] = nq;
fa[np] = nq;
while (p && ch[p][c] == q)
{
ch[p][c] = nq;
p = fa[p];
}
ch[nq] = ch[q];
}
}
}
// 抽取后缀树
void buildtree()
{
edg.resize(pid + 1);
for (int i = 2; i <= pid; i++)
{
edg[fa[i]].emplace_back(i);
}
}
// 获取子串出现次数
void getcnt(int u)
{
for (auto& v : edg[u])
{
getcnt(v);
cnt[u] += cnt[v];
}
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
SAM sam(s.size());
for (auto& i : s) sam.extend(i);
sam.buildtree();
sam.getcnt(1);
ll res = 0;
for (int i = 1; i <= sam.pid; i++)
{
if (sam.cnt[i] > 1) res = max(res, sam.cnt[i] * sam.len[i]);
}
cout << res << endl;
return 0;
}字典序第 k 大子串
求出通过每个节点的子串数量后。判断当前节点是否包含第k大子串，不断向后选择节点，重复。
题目：P3975 [TJOI2015] 弦论（https://www.luogu.com.cn/problem/P3975）
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
using ll = long long;
struct SAM
{
vector<vector<int>> edg, ch;
vector<ll> fa, len, cnt, dp;
int pid = 1, np = 1;
SAM(int size)
{
int est = size * 2 + 5;
ch.resize(est, vector<int>(26));
cnt.resize(est, 0);
len.resize(est, 0);
fa.resize(est, 0);
dp.resize(est, -1);
}
// 建立后缀自动机
void extend(int c)
{
c -= 'a';
int p = np;
np = ++pid;
len[np] = len[p] + 1;
cnt[np] = 1;
while (p && !ch[p][c])
{
ch[p][c] = np;
p = fa[p];
}
if (p == 0) fa[np] = 1;
else
{
int q = ch[p][c];
if (len[q] == len[p] + 1) fa[np] = q;
else
{
int nq = ++pid;
len[nq] = len[p] + 1;
fa[nq] = fa[q];
fa[q] = nq;
fa[np] = nq;
while (p && ch[p][c] == q)
{
ch[p][c] = nq;
p = fa[p];
}
ch[nq] = ch[q];
}
}
}
// 抽取后缀树
void buildtree()
{
edg.resize(pid + 1);
for (int i = 2; i <= pid; i++)
{
edg[fa[i]].emplace_back(i);
}
}
// 获取子串出现次数
void getcnt(int u)
{
for (auto& v : edg[u])
{
getcnt(v);
cnt[u] += cnt[v];
}
}
// 经过某点的不同子串数
ll getdp(int u)
{
if (dp[u] != -1) return dp[u];
dp[u] = cnt[u];
for (int i = 0; i < 26; i++)
{
if (ch[u][i]) dp[u] += getdp(ch[u][i]);
}
return dp[u];
}
};
void query(SAM& sam, int u, int k)
{
if (k <= sam.cnt[u]) return;
k -= sam.cnt[u];
for (int i = 0; i < 26; i++)
{
ll v = sam.ch[u][i];
if (!v) continue;
if (k > sam.dp[v]) k -= sam.dp[v];
else
{
cout << (char)('a' + i);
query(sam, v, k);
break;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t, k;
string s;
cin >> s >> t >> k;
SAM sam(s.size());
for (auto& i : s) sam.extend(i);
if (t)
{
sam.buildtree();
sam.getcnt(1);
}
else
{
for (int i = 1; i <= sam.pid; i++) sam.cnt[i] = 1;
}
sam.cnt[1] = 0;
sam.getdp(1);
if (k > sam.dp[1]) cout << "-1" << endl;
else
{
query(sam, 1, k);
cout << endl;
}
return 0;
}后缀数组 (SA)
这个部分目前按照博主智商实在无法理解，只得后面补上了。。。
目前有关字符串的子串相关问题就这些内容。希望我以后遗忘可以慢一点。。。同时如果这也能帮到你，我很荣幸。真的。。
版权声明：
作者：Toms Project
链接：https://blog.projectoms.com/pages/1685.html
来源：Toms Project 官方博客
文章版权归作者所有，未经允许请勿转载。
THE END
二维码
打赏
文章目录
关闭
共有 0 条评论