最长相同子串

给定两个字符串，输出最长相同子串:
方法1:暴力破解

#include<iostream>
#include<vector>
#include<algorithm>
#include<sstream>
#include<string>
using namespace std;
string lagestcommonsubset(const string &a,const string &b){
	
	int max_length=0;
	string res;
	for(int i=0;i<a.length();i++){
		for(int j=0;j<b.length();j++){
			int pos1=i;
			int pos2=j;
			int length=0;
			
			while(pos1<a.length()&&pos2<b.length()){
				if(a[pos1]==b[pos2])
				{
				    pos1++;pos2++;
				    length++;
				}
				    
				else{
					if(length>max_length){
						max_length=length;
						res=a.substr(i,length);
					}
					length=0;
					break; 
				}//else
				
			}//while
			if(length>max_length){
				max_length=length;
				res=a.substr(i,length);
			}
		}//for
	}//for
	return res;
}
int main(){
	string a,b;
	cout<<"输入两个字符串,可以包含空格:"<<endl;
	getline(cin,a);
	getline(cin,b);
	cout<<lagestcommonsubset(a,b);
}

(2)动态规划,空间复杂度为O(n²)，时间复杂度为O(n²),算法思想:a的第i+1个位置结尾的子串和b的第j+1个位置结尾的子串最大相同长度为a的以位置i结尾和b的以位置j结尾的最大相同子串长度+1，状态转移式为dp[i+1,j+1]=dp[i,j]+1。

#include<iostream>
#include<vector>
#include<algorithm>
#include<sstream>
#include<string>
using namespace std;
string lagestcommonsubset(const string &a,const string &b){
	   int m=a.length(),n=b.length();
       vector<vector<int>>dp(m+1,vector<int>(n+1,0));
       int max_len=0,pos=-1;
       for(int i=0;i<a.length();i++){
       	for(int j=0;j<b.length();j++){
       		if(a[i]==b[j]){
       			dp[i+1][j+1]=dp[i][j]+1;
       			if(dp[i+1][j+1]>max_len){
       				max_len=dp[i+1][j+1];
       				pos=i;
				   }
			   }
		   }
	   }//for
	   return a.substr(pos-max_len+1,max_len);
}
int main(){
	string a,b;
	cout<<"输入两个字符串,可以包含空格:"<<endl;
	getline(cin,a);
	getline(cin,b);
	cout<<lagestcommonsubset(a,b);
}

(3)动态规划:空间复杂度为O(n)，时间复杂度为O(n²),思想同方法2，但是只用一个一维数组来存储字符串b的每个位置j结尾与当前字符串a的位置i结尾的最大相同子串长度，如求b对应a的以位置i+1结尾的最大相同子串长度时，对b的位置j从后往前求取当前对应a的位置i+1的最大子串长度，当更新到位置j+1时，位置j的值dp[j]为b的位置j结尾对应a的位置i结尾的最大相同子串长度。状态转移公式为:dp[j+1]=dp[j]+1，注意，若a[i+1]和b[j+1]不同，则令dp[j+1]=0，不然dp[j+1]会是对应a[i]结尾的最大相同子串长度。

#include<iostream>
#include<vector>
#include<algorithm>
#include<sstream>
#include<string>
using namespace std;
    string lagestcommonsubset(const string &a,const string &b){
          int m=a.length(),n=b.length();
          vector<int>dp(n+1);
          int max_len=0,pos=-1;
          for(int i=0;i<a.length();i++){
            for(int j=b.length()-1;j>=0;j--){
                if(a[i]==b[j]){
                    dp[j+1]=dp[j]+1;
                    if(dp[j+1]>max_len){
                        max_len=dp[j+1];
                        pos=j;
                      }
                  }
                else{
                    dp[j+1]=0;
                }
              }
          }//for
          return b.substr(pos-max_len+1,max_len);
    }

int main(){
    string a,b;
    cout<<"输入两个字符串,可以包含空格:"<<endl;
    getline(cin,a);
    getline(cin,b);
    cout<<lagestcommonsubset(a,b);
}