2019-ACM-ICPC 徐州网络赛 M. Longest subsequence 序列自动机

String is a very useful thing and a subsequence of the same string is equally important.

Now you have a string ss with length nn and a string tt with length mm. Find out the longest subsequence in the string ss so that the lexicographical order of this subsequence is strictly larger than tt.

Input

two integers nn, mm in the first line 

（All characters are lowercase letters）

The second line is a string ss

The third line is a string tt

• 1 \le n,m \le 10^61≤n,m≤106

Output

Output an integer representing the longest length, otherwise output -1.

样例输入1复制

样例输出1复制

样例输入2复制

样例输出2复制

题意：

给你两个字符串S, T。问S串的子序列字典序严格>T的字典序的子序列最大长度？

分析：

序列自动机预处理出来每一个位置后面其最近的字母的位置是什么，即pos[i][j]数组，可以求出主串S第i个位置字母j在后面出现的第一个位置。

对于str2每一个字符来说，我们可以有两种选择：

1. 选择比str2[i]大的，则剩下的都可以选,
2. 选择跟str2[i]一样的，只有最后剩下的字符才能算比其字典序大。

具体看代码把

#include<bits/stdc++.h>
using namespace std;

const int N=1000005;
typedef long long LL;
int pos[N][30];
void getpos(char str1[])
{
    int len1=strlen(str1+1);      
    
    for(int i=0;i<26;i++)
    	pos[len1][i]=len1+1;
    for(int i=len1; i>=1; i--)
    {
        for(int j=0; j<26; j++)
        {
            pos[i-1][j]=pos[i][j];
        }
        pos[i-1][str1[i]-'a']=i;
    }
}
char str1[N],str2[N];
bool judge(char str2[])
{
    int len1=strlen(str1+1); 
    int len2=strlen(str2+1);
    int p=0;
    for(int i=1; i<=len2; i++)
    {
        p=pos[p][str2[i]-'a'];
        if(p==len1+1)
            return 0;
    }
    return 1;
}
 int len1,len2;
void out()
{
	for(int i=0;i<=len1;i++)
	{
		for(int j=0;j<26;j++)
		{
			cout<<pos[i][j]<<" ";
		}
		cout<<endl;
	}
}
int main()
{
   
    scanf("%d%d",&len1,&len2);
    scanf("%s",str1+1);
    getpos(str1);
    //out();
    
    scanf("%s",str2+1);
    
    int cur=0;
    LL ans=-1;
    
    for(int i=1;i<=len2;i++)
	{
		for(char j=str2[i]+1;j<='z';j++)
		{
			int p=pos[cur][j-'a'];
			if(p<len1+1)
				ans=max(ans,(LL)len1-p+1+i-1);	
			//cout<<ans<<" "<<p<<" "<<j<<endl;
		}
		cur=pos[cur][str2[i]-'a'];
	    //cout<<cur<<" "<<str2[i]-'a'<<endl;
		if(cur>=len1+1) break;


	}
	
	if(cur+1<len1+1) ans=max(ans,(LL)len1-cur+1+len2-1);

    printf("%lld\n",ans);
    return 0;
}