子序列自动机
title: 子序列自动机
categories:
- ICPC
tags:
- null
abbrlink: df3bb3f1
date: 2023-11-09 00:00:00
子序列自动机
判断s是不是t的子序列
bool isSubsequence(string s, string t) {
int m = t.size();
vector<array<int, 26>> next(m + 2);
t = " " + t;
for (int i = m; i >= 1; i--) {
for (int j = 0; j < 26; j++) {
if (j == t[i] - 'a')
next[i][j] = i + 1;
else {
next[i][j] = next[i + 1][j];
}
}
}
int p = 1;
for (auto x : s) {
p = next[p][x - 'a'];
}
if (p)
return true;
return false;
}
t最少由多少个个s的子序列拼接而成
int catseq(string s, string t) {
int m = t.size();
vector<array<int, 26>> next(m + 2);
t = " " + t;
for (int i = m; i >= 1; i--) {
for (int j = 0; j < 26; j++) {
if (j == t[i] - 'a')
next[i][j] = i + 1;
else {
next[i][j] = next[i + 1][j];
}
}
}
int p = 1;
int ans = 1;
deb(s);
for (auto x : s) {
p = next[p][x - 'a'];
deb(p);
if (p == 0) {
ans++;
p = 1;
p = next[p][x - 'a'];
if (p == 0)
return -1;
}
}
return ans;
}
void solve() {
string s, t;
cin >> s >> t;
cout << catseq(t, s) << endl;
}
本质不同子序列个数
void solve() {
int n;
cin >> n;
vector<int> dp(n + 1); // 前i个数的不同子序列个数
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
map<int, int> mp;
for (int i = 1; i <= n; i++) {
if (mp.count(a[i]) == 0)
dp[i] = 2 * dp[i - 1] + 1;
else {
int last = mp[a[i]];
dp[i] = 2 * dp[i - 1] - dp[last - 1];
}
dp[i] %= mod;dp[i]+=mod;dp[i]%=mod;
mp[a[i]] = i;
}
cout << dp[n] << endl;
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!