序列自动机

1.PIPIOJ--1343: PIPI的字符串问题Ⅰ 链接标题
题目简述：对于一个字符串s,给定q次询问，问字符串t是不是其子序列。
思路：用序列自动机，序列自动机是一个二维数组，这里用Next[i][j]表示，含义是距离位置i的第j个字母(j=0表示'a',以此类推，j=25表示'z')的位置是多少。建立序列自动机是从后往前建立，每一次循环都是Next[i][j]继承Next[i+1][j],然后更新位置i所表示字母的位置(即当前位置)。
小收获：这里两个字符串是s,t都应从s+1,t+1处读入，这样如下代码中的now变量为0就可以表示某个字母不存在的情况。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int Next[N][26];
char s[N],t[N];
int main()
{
    scanf("%s",s+1);
    int len1=strlen(s+1);
    for(int i=len1;i>=1;i--)
    {
        for(int j=0;j<26;j++)
        Next[i][j]=Next[i+1][j];
        Next[i][s[i]-'a']=i;
    }
    int q;
    scanf("%d",&q);
    while(q--)
    {
        scanf("%s",t+1);
        int len2=strlen(t+1),now=1;
        for(int i=1;i<=len2;i++)
        {
            now=Next[now][t[i]-'a'];
            if(!now) break;
            now++;
        }
        if(!now) printf("No\n");
        else printf("Yes\n");
    }
 } 

2.PIPIOJ--1039: 重复子序列问题 链接标题
题目简述：给定字符串s,t。问至少s串需要重复多少次才能使得t是s的子序列。
思路：对串s使用一次序列自动机，这里重复就是用now变量重新从头开始来替换。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
char s[N],t[N];
int Next[N][26];
int main()
{
    while(scanf("%s%s",s+1,t+1)!=EOF)
    {
        memset(Next,0,sizeof(Next));
        int len1=strlen(s+1),len2=strlen(t+1);
        for(int i=len1;i>=1;i--)
        {
            for(int j=0;j<26;j++)
            Next[i][j]=Next[i+1][j];
            Next[i][s[i]-'a']=i;
        }
        int now=1,ans=1,start=1,flag=0;
        for(int i=1;i<=len2;i++)
        {
            if(!Next[start][t[i]-'a'])
            {
                flag=1; 
                break;
            } 
            now=Next[now][t[i]-'a'];
            if(!now)
            {
                ans++;
                now=Next[start][t[i]-'a'];
                now++;
            }
            else now++;
         }
        if(flag) printf("-1\n");
        else printf("%d\n",ans); 
    }
}