序列自动机
文章目录
解释
好难解释
它是一个"简单"的链表
给一个字符串,将这个字符串里面所有的字母都进行标记(利用数组模拟的链表)
(首先是不是应该学一下链表?)
标记过后,在从前往后对这个字符串扫描的过程中,就可以很快的找到需要的子序列
-
为什么可以很快找到需要的子序列
- 因为在标记的过程中,我们标记了当前字符最近的下一个二十六个字符的任意字符的位置
-
比如abcdefg这个字符串,在标记过后,a这个字符拥有的信息是:
- b在2号位,c在3号位,d在4号位....即
input[1][2]=2;input[1][3]=3;input[1][4]=4 - 没有更多的a即
input[1][1]=0! -
这样,我们在找ac这个子序列的时候,就优化成了以下情况
- 从头开始遍历,发现a字符
- 搜刮a字符身上的信息,发现有下一个c字符且c字符在3号位
- 指针跳转到3号位
- 检查是否找完
- 结束
-
如果找az这样一个子序列,情况是这样的
- 从头开始遍历,发现a字符
- 搜刮a字符身上的信息,发现原串中没有下一个z字符
- 子序列不存在
- 结束
- b在2号位,c在3号位,d在4号位....即
例题
判断一次的
https://ac.nowcoder.com/acm/contest/1083/B
- 题意:
问字符串t是否作为一个子序列在s中出现,要求O(n)时间复杂度
解释一下子序列(subsequence)和子串(substring)的区别
子串必须是连续的一段,和字符串上子区间是同一个意思
子序列不必是连续的(但也要有顺序),可以是间断的
比如串“acdef”就有子序列“aef”,但是没有子串“aef”
- 题解
贪心!
在s串中从头开始找,先去找t串的第一个字符,再去找第二个字符
每找到一个位置就往后继续找,保证每一次找到的位置都离上一个找到的位置最近
比如s = ababcbzaa,t = abzaa
从头开始找a,发现s串第一个位置就是a
然后从第一个位置往后找最近的b,之后找最近的z…..以此类推
运用这种贪心的思想,如果能够找全,那么t串就是s串的一个子序列
按照这种贪心的思想,就可以在O(n)的时间复杂度内做完这题
只需要扫一遍s串就可以了
但是如果把这题改一下,如果s串特别特别长,t串特别特别短
然后会有q个查询,每次都输入一个新的t串(s串只有一个)
让你做出q次回答,每次回答输入的t串是不是s串的子序列
这时候如果你每次都扫一遍s串,复杂度就是O(n * q)的
序列自动机的作用就是可以在这里把复杂度优化成O(所有t串的长度之和)
- Answer 1
//序列自动机——贪心,找最近的!!!!
//提前记录a的下一个a,b,c,d,e...z在哪里
//子序列——不连续
//子串——连续
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long long ll;
const int maxn=1e5+5;
char s[maxn];
char t[maxn];
//写在里面——避免冲突
//写两个的时候sq1,sq2;
struct seqam{
//26 characters
int nxt [maxn][26];
//z e a
//e:a-3
//z:a-3
void build (){
int len =strlen(s+1);
memset(nxt[len],0,sizeof(nxt[len]));
for(int i=len;i>0;i--){
for(int j=0;j<26;j++){
nxt[i-1][j]=nxt[i][j];
}
nxt[i-1][s[i]-'a']=i;
}
}
void solve(){
int len=strlen(t+1);
int p=0;//root?super?
for(int i=1;i<=len;i++){
if(!nxt[p][t[i]-'a']){
cout<<"NO"<<endl;
return;
}
p=nxt[p][t[i]-'a'];
}
cout<<"YES"<<endl;
}
}seq;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
lli n,q;
cin>>n>>q;
cin>>s+1;
seq.build();
while(q--) {
cin >> t + 1;
seq.solve();
}
return 0;
}
- Answer 2
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int nxt[N][26], cur[26]; char s[N];
int main() {
int n, q;
scanf("%d%d%s", &n, &q, s + 1);
for (int i = n; i >= 0; cur[s[i] - 'a'] = i, i--)//cur作为中介保存一列的信息
memcpy(nxt[i], cur, sizeof(cur));
while (q--) {
scanf("%s", s + 1);
int m = strlen(s + 1);
int t = 0;
bool flag = true;
for (int i = 1; i <= m; i++) {
if (nxt[t][s[i] - 'a'])
t = nxt[t][s[i] - 'a'];
else {
flag = false;
break;
}
}
puts(flag ? "YES" : "NO");
}
return 0;
}
判断多次
https://codeforces.com/contest/1295/problem/C
- 题意
输入两个字符串,s串和t串,一种操作:每次从s串中选取一个子序列
问最少从s串中选取几次子序列能拼成t串,输出这个最小次数
选不出来输出-1
#include <bits/stdc++.h>
using namespace std;
const int N=int(2e5)+99;
const int INF=int(1e9)+99;
int tc;
string s,t;
int nxt[N][26];
int main(){
cin>>tc;
//构建序列自动机,INF表示无 相当于false
while(tc--){
cin>>s>>t;
for(int i=0;i<s.size()+1;i++){
for(int j=0;j<26;j++){
nxt[i][j]=INF;
}
}
for(int i=int(s.size())-1;i>=0;i--){
for(int j=0;j<26;j++){
nxt[i][j]=nxt[i+1][j];
}
nxt[i][s[i]-'a']=i;
}
//
int res=1,pos=0;
for(int i=0;i<t.size();i++){//从字符串头开始遍历
if(pos==s.size()){//指针指向最后,完成了一次取子串
pos=0;
res++;
}
// cout<<"pos1 "<<pos<<endl;
if(nxt[pos][t[i]-'a']==INF) {//没找完,从头开始 令序列指针为首元素
pos = 0;
res++;
}
if(nxt[pos][t[i]-'a']==INF&&pos==0){//没有这个字母,就是找不到
res=INF;
break;
}
pos=nxt[pos][t[i]-'a']+1;//pos的位置
// cout<<"pos2 "<<pos<<endl;
}
if(res>=INF) cout<<"-1"<<endl;
else cout<<res<<endl;
// cout<<"res "<<res<<endl;
}
return 0;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论