序列自动机

介绍

子串：串中任意个连续的字符组成的子序列称为该串的子串
子序列：子序列中的字符在字符串中不一定是连在一起的，而是删除其中若干个， 但子序列一定是单调的
简单说就是子序列不连续，子串连续

序列自动机可以在复杂度为O（n）下判断一个串是不是另一个串的子序列

序列自动机的本质其实就是空间换时间，因为暴力做完全也是可以的，但是会超时，dp做的话还容易超空间

所需数组：
next[i][j] ：j的范围为（0~25）即对应26个英文字母。表示原串s的第i位后面那26个字母j出现的最早的位置
也就是next指向的是下一个j的坐标，这样的话把next的值带入下一个next[i][j]中的j，就可以一直向下找

你可以理解成建了一棵树，一直向外伸长树枝，相连在一起

那如何建树呢？
next存的是最早出现的字符，我们可以倒着建，将后面的赋给前面
我们用next[i+1][j]赋给next[i][j],找到第i个字符后面的26个字母最早出现的位置
next[i][s[i]-'a']=i
然后把当前字符更新到当前字符在原串中从后向前最晚出现的位置

    for (int i = n; i >= 1; i--)
    {
         for (int j = 0; j < 26; j++) nxt[i][j] = nxt[i + 1][j];
         int w=str[i]-'a';
          nxt[i][w] = i;
    }

查找时可以这样：

        int now = nxt[i][mark[pos++] - 'a'];
        while (now != -1 && pos < 10) 
        {
          now = nxt[now][mark[pos++] - 'a'];
        }

例题：
例题