LCS的一维实现方法：

#include<bits/stdc++.h>
using namespace std;
string a,b;
int la,lb;
int f[300001];
int main()
{
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	
	cin>>a>>b;
	if(a.size()>b.size()) swap(a,b);
	la=a.size();
	lb=b.size();
	for(int i=0;i<la;i++)
	{
		int maxlong=0;
		for(int j=0;j<lb;j++)
		{
			
			int z=maxlong;
			if(b[j]==a[i]) 
			{
				maxlong=max(f[j],maxlong);
				f[j]=z+1;
					
			}
			else
			maxlong=max(f[j],maxlong);
		}
	}
	int ans=0;
	for(int i=0;i<lb;i++)
	ans=max(ans,f[i]);
	cout<<ans-1;
 }