C++

C++ – 序列自动机

_Redstone_c_

模板题：https://nanti.jisuanke.com/t/38232

可以求出一个序列中是否存在某个子序列

基本思想

定义一个next数组，用来存储在第i位后面出现的序列中的某一个元素的出现位置。

例如字符串abcdefg[字符串下标从一开始]

可以得到next的内容为：

next[0]['a'] = 1;    next[1]['a'] = -1;   next[2]['a'] = -1;    ......
next[0]['b'] = 2;    next[1]['b'] = 2;    next[2]['b'] = -1;    ......
next[0]['c'] = 3;    next[1]['c'] = 3;    next[2]['c'] = 3;     ......
next[0]['d'] = 4;    next[1]['d'] = 4;    next[2]['d'] = 4;     ......
next[0]['e'] = 5;    next[1]['e'] = 5;    next[2]['e'] = 5;     ......
next[0]['f'] = 6;    next[1]['f'] = 6;    next[2]['f'] = 6;     ......
next[0]['g'] = 7;    next[1]['g'] = 7;    next[2]['g'] = 7;     ......

然后在查询其子序列是否存在时，只要找到子串第i个元素出现的位置[记做j]，然后在next中查找j开始的子串中i+1个元素是否存在即可。

优化思想

在建立next数组时，可以从后往前遍历主串，并用last数组记录当前的i以后第一个出现的序列中的元素位置，并不停刷新到next就可以在O(n)下求出next。

[要空出next[0]来储存整串中数值最早出现的数的位置]

代码

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int MAXN = 100000 + 100;
const int MAXC = 26;
int nxt[MAXN][MAXC];
int last[MAXC];
int main() {
    string T;
    T.resize(MAXN);
    scanf(%s, &T[0]);
    T =   + T;
    memset(last, -1, sizeof last);
    int len = strlen(T.c_str());
    for(int i = len - 1; i >= 0; i--) {
        for(int j = 0; j < MAXC; j++)
            nxt[i][j] = last[j];
        if(i == 0) continue;
        last[T[i] - 'a'] = i;
    }
    int m;
    scanf(%d, &m);
    while(m--) {
        string temp;
        temp.resize(MAXN);
        scanf(%s, &temp[0]);
        int templen = strlen(temp.c_str());
        bool b = true;
        int tempn = 0;
        for(int i = 0; i < templen; i++) {
            tempn = nxt[tempn][temp[i] - 'a'];
            if(tempn == -1) {
                printf(NO\n);
                b = false;
                break;
            }
        }
        if(b) printf(YES\n);
    }
    return 0;
}

发表回复