经典例题：求最长子串（两个串和一个串）

一个串

找出字符串的最长子串，要求字串的所有字符相同，如：”abcdeeefgh”结果是”eee”

解题:

public class TestStr {
    public static void main(String args[]){
        String s = "abcdeeefgh";
        String result = "";
        int count = 0;
        int max = count;
        int i,j;
        for(i = 0; i < s.length(); i++){
            for(j = i + 1; j < s.length(); j++){
                if(s.charAt(i) == s.charAt(j)){
                    count++;
                }
                else
                    break;
            }
            if(count > max){
                max = count;
                result = s.substring(i,j);
            }
            count = 0;
        }
        System.out.println(result);
    }
}

 两个串

两个字符串的最长子串

解题：

#include <iostream>
using namespace std;
const int N = 1000;

char* FirstMaxSubString(const char *str1,char *str2)
{
	int pos;  //存放第一个最长子串的起始位置
	int max = 0;  //第一个最长子串的长度
	int i,j;
	for(i=0;str1[i];i++)
	{
		for(j=0;str2[j];j++)
		{
			for(int k=0;str1[i+k]==str2[j+k] && (str1[i+k] || str2[i+k]);k++)
				if(k>max)
				{
					pos = j;
					max = k+1;
				}
		}
	}
	
	char *result = new char[max+1];
	for(i=0;i<max;i++)
		result[i] = str2[pos++];
	result[i] = '/0';
	return result;
	//或者直接用下面的语句返回，好处是不用申请空间
	/*str2[pos+max] = '/0';
	return (char *)(str2+pos);*/
}

int main()
{
	char *str1 = new char[N];
	char *str2 = new char[N];
	cout<<"string_1:";
	cin.getline(str1,N);
	cout<<"string_2:";
	cin.getline(str2,N);
    //固定测试例
	/*
	char *str1 = "abractyeyt";
	char *str2 = "dgdsaeactyey";
	*/
	cout<<"FirstMaxSubString:"<<FirstMaxSubString(str1,str2)<<endl;
	return 0;
}

动态规划：

char str1[]="abractyeyt";
char str2[]="dgdsaeactyey";
#define N sizeof(str1)-2
#define W sizeof(str2)-2
int path[N][W];
int sum=0;
int t=0;
	int begin;
int LCS_2(char *str1,char *str2,int len1,int len2)
{
	if(len1<=0||len2<=0)
		return 0;
	else
	{
		for(int i=0;i<len1;i++)
		{
			for(int j=0;j<len2;j++)
			{
				if(str1[i]==str2[j])
				{
					path[i+1][j+1]=path[i][j]+1;
				}
				else
				{
					path[i+1][j+1]=0;
				}
				if(path[i+1][j+1]>sum)
				{
					begin=i-sum;
					sum=path[i+1][j+1];
				}
			}
		}
	}
	return sum;
}
int LCS_1(char *str1,char *str2,int len1,int len2)
{
	if(len1<=0||len2<=0)
		return 0;
	for(int i=1;i<=len1;i++)
	{
		for(int j=1;j<=len2;j++)
		{
		//	if(*(str1+i-1)==*(str2+j-1))
			if(str1[i-1]==str2[j-1])
			{
				path[i][j]=path[i-1][j-1]+1;
			}
			else
			{
				path[i][j]=0;
			}
			if(path[i][j]>=sum)
				sum=path[i][j];
		}
	}
	return sum;
}

int LCS(char *str1,char *str2,int len1,int len2)
{
	if(len1<=0||len2<=0)
		return 0;
	for(int i=0;i<len1;i++)
	{
		for(int j=0;j<len2;j++)
		{
			if(*(str1+len1-1)==*(str2+len2-1))
			{
				path[len1-1][len2-1]=1;
				return LCS(str1,str2,len1-1,len2-1)+1;
			}
			else
			{
				int a=LCS(str1,str2,len1,len2-1);
				int b=LCS(str1,str2,len1-1,len2);
				if(a>b)
				{
					path[len1-1][len2-1]=2;
				}
				else
					path[len1-1][len2-1]=-1;
				return a>b?a:b;
			}
		}
	}
}
void Print_1(int m)
{
	int i=0;
	while(i<m)
	{
		cout<<*(str1+begin+i++);
	}
}
void Print()
{
	std::stack<char> st;
	//for(int i=0;i<=N;i++)
	//{
	//	for(int j=0;j<=W;j++)
	//		cout<<path[i][j]<<" ";
	//	cout<<endl;
	//}
	//cout<<endl;
	int i=N,j=W;
	while(i>=0&&j>=0)
	{
		if(path[i][j]==-1)
		{
			i=i-1;
		}
		else if(path[i][j]==1)
		{
			st.push(str2[j]);
			i--;
			j--;
		}
		else
			j=j-1;
	}
	while(!st.empty())
	{
		cout<<st.top();
		st.pop();
	}
	cout<<endl;
}
int main()
{
	int m=LCS_2(str1,str2,strlen(str1),strlen(str2));
	cout<<m<<endl;
	Print_1(m);
	cout<<endl;
	cout<<LCS(str1,str2,strlen(str1),strlen(str2))<<endl;
	Print();
	return 0;
}