Longest subsequence【思维+序列自动机】

题意：

给出两个字符串 \(s\) 和 \(t\)，求 \(s\) 中字典序严格大于串 \(t\) 的子序列的最长的长度。
题目链接：https://nanti.jisuanke.com/t/41395

分析：

先用序列自动机，处理出一个数组：\(nxt[i][j]\)，表示位置 \(i\) 后面的最近的字母 \(j\) 的位置。那么，对 \(s\) 串，有两种选择：
1.选择比 \(t[i]\) 大的，则剩下的都可以选；
2.选择跟 \(t[i]\) 一样的，那么就要一直向后取，直到取完；

代码：

#include<bits/stdc++.h>

using namespace std;
const int N=1e6+6;
char A[N],B[N];
int now[30],nxt[N][30];
void init(char s[],int len)
{
    memset(now,-1,sizeof(now));
    for(int i=len-1;i>=0;i--)
    {
        for(int j=0;j<26;j++)
            nxt[i][j]=now[j];
        now[s[i]-'a']=i;
    }
}
int main()
{
    int n,m,cnt=0;
    scanf("%d%d",&n,&m);
    scanf("%s",A);
    scanf("%s",B);
    init(A,n);
    int ans=-1;
    for(int i=B[0]-'a'+1;i<26;i++)
    {
        if(now[i]==-1) continue;
        ans=max(ans,n-now[i]);
    }
    if(now[B[0]-'a']==-1)//
    {
        printf("%d\n",ans);
        return 0;
    }
    int start=now[B[0]-'a'];
    for(int i=1;i<m;i++)
    {
        for(int j=B[i]-'a'+1;j<26;j++)
        {
            if(nxt[start][j]==-1) continue;
            ans=max(ans,n-nxt[start][j]+i);
        }
        if(nxt[start][B[i]-'a']==-1)
            break;
        start=nxt[start][B[i]-'a'];
        if(i==m-1&&start<n-1)
            ans=max(ans,n-start+i);
    }
    printf("%d\n",ans);
    return 0;
}