最长公共子串，传统算法是O(n*m)，我们可以对b中每一个字符在a中找到它出现的位置，构成一个新串，对新串用LIS就得到了最长公共子串nlogn、
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
template<class T>
int bsearch(T c[],int n,T a)
{
int l=1, r=n;
while(l<=r)
{
int mid = (l+r)/2;
if( a > c[mid] && a <= c[mid+1] )
return mid+1;
else if( a < c[mid] )
r = mid-1;
else l = mid+1;
}
}
template<class T>
int LIS(T a[], int n)
{
int i, j, size = 1;
T *c=new T[n+1];
int *dp=new int[n+1];
c[1] = a[1]; dp[1] = 1;
for(i=2;i<=n;++i)
{
if( a[i] <= c[1] ) j = 1;
else if( a[i] >c[size] )
j=++size;
else
j = bsearch(c, size, a[i]);
c[j] = a[i]; dp[i] = j;
}
return size;
}
int a[1000000];
int v[1000000];
int main()
{
int cas,ca=1,n,m,k;scanf("%d",&cas);
while(cas--)
{
int top=0;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m+1;i++)
{
scanf("%d",&n);
v[n]=i;
}
for(int i=1;i<=k+1;i++)
{
scanf("%d",&n);
if(v[n]) a[++top]=v[n];
}
printf("Case %d: %d\n",ca++,LIS(a,n));
}
return 0;
}