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
9 3 aaabbbccc abc
样例输出1
6
样例输入2
9 3 aaabbbccc zzz
样例输出2
-1
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+10; int n,m; char s[maxn],t[maxn]; int nx[maxn][26]; int main() { scanf("%d%d",&n,&m); scanf("%s%s",s+1,t+1); for(register int i=0;i<26;++i){ nx[n][i]=nx[n+1][i]=n+1; } for(register int i=n-1;i>=0;--i){ for(register int j=0;j<26;++j){ nx[i][j]=nx[i+1][j]; } int to=s[i+1]-'a'; nx[i][to]=i+1; } int res=-1,cur=0; for(register int i=1;t[i];++i){ int pos=t[i]-'a'; for(register int j=pos+1;j<26;++j){ int id=nx[cur][j]; if(id<=n){ res=max(res,n-id+1+i-1); } } cur=nx[cur][pos]; if(cur>n)break; } if(cur<n)res=max(res,m+n-cur); printf("%d\n",res); return 0; }