最长公共子串与最长连续子串算法

男娘i 2022-08-11 16:44 328阅读 0赞

利用DP思想

最长公共子串中result\[i\]\[j\]存放str1前i个与result\[j\]个的最长公共子串，当str1\[i + 1\]==str2\[j + 1\]时，str1前i+1与str2前j+1个即result\[i + 1\]\[j + 1\] = result\[i\]\[j\] + 1,否则就是str1前i个与str2前j + 1个的公共子串与str1前i+1与str2前j个的公共子串的最大值，即max(result\[i\]\[j + 1\],result\[i + 1\]\[j\]);

最长连续子串中result\[i\]\[j\]存放str1前i个与str2前j个中，他们的公共子串是以str\[i\]或str\[j\]结尾的最长连续子串长度。当str1\[i + 1\] == str2\[j + 1\]时，result\[i + 1\]\[j + 1\] = result\[i\]\[j\] + 1;否则为0（因为两个字符串后缀不同）

/*
       VC6.0下编译
    */
    #include<iostream>
    #include<stack>
    #include<string>
    using namespace std;
    int max(int a,int b)
    {
    	return a<b?b:a;
    }
    int Longest_Common_Substring(string str1,string str2)
    {
    	int **result = new int*[str1.length()];
    	int LCS_SUM = 0;
    	for(int i = 0; i < str1.length(); ++i)
    		result[i] = new int[str2.length()];
    	//初始化第1行和第1列的值
    	int common_str1 = 0;
    	for(i = 0;i < str1.length();++i)
    	{		
    		if(str2[0] == str1[i] && common_str1 != 1)
    		{
    			result[i][0] = 1;
    			common_str1++;
    		}
    		result[i][0] = common_str1;
    	}
    	int common_str2 = 0;
    	for(i = 0;i < str2.length();++i)
    	{
    		if(str1[0] == str2[i] && common_str2 != 1)
    		{
    			result[0][i] = 1;
    			common_str2++;
    		}
    		result[0][i] = common_str2;
    	}
    	for(i = 1; i < str1.length();++i)
    		for(int j = 1; j < str2.length();++j)
    		{
    			if(str1[i] == str2[j])
    			{
    				result[i][j] = result[i - 1][j - 1] + 1;
    				if(LCS_SUM < result[i][j])
    					LCS_SUM = result[i][j];
    			}
    			else result[i][j] = max(result[i][j - 1],result[i - 1][j]);
    		}
    	for(i = 0;i < str1.length();++i)
    	{
    		for(int j = 0;j < str2.length();++j)
    			cout<<result[i][j]<<" ";
    		cout<<endl;
    	}
    	for(i = 0;i < str1.length();++i)
    	{
    		delete[str2.length()] result[i];
    		result[i] = NULL;
    	}
    	delete[str1.length()] result;
    	result = NULL;
    	return LCS_SUM;
    }
    int Longest_Consecutive_Substring(string str1,string str2)
    {
    	int **result = new int*[str1.length() + 1];
    	int LCS_SUM = 0;
    	for(int i = 0; i < str1.length() + 1; ++i)
    	{
    		result[i] = new int[str2.length() + 1];
    		for(int j = 0;j < str2.length();++j)
    			result[i][j] = 0;
    	}
    	for(i = 1;i < str1.length() + 1;++i)
    		for(int j = 1;j < str2.length() + 1;++j)
    		{
    			if(str1[i - 1] == str2[j - 1])
    			{
    				result[i][j] = result[i - 1][j - 1] + 1;
    				if(LCS_SUM < result[i][j])
    					LCS_SUM = result[i][j];
    			}
    			else result[i][j] = 0;
    		}
    	for(i = 0;i < str1.length() + 1;++i)
    	{
    		delete[str2.length() + 1] result[i];
    		result[i] = NULL;
    	}
    	delete[str1.length()] result;
    	result = NULL;
    	return LCS_SUM;
    }
    int main()
    {
    	string str1,str2;
    	while(cin>>str1>>str2)
    	{
    		cout<<"最长公共子串长度"<<Longest_Common_Substring(str1,str2)<<endl;
    		cout<<"最长连续子串长度"<<Longest_Consecutive_Substring(str1,str2)<<endl;
    	}
    	return 0;
    }