学步园

35、编程实现：找出两个字符串中最大公共子字符串,如"abccade","dgcadde"的最大子串为
"cad"

/*
35、编程实现：找出两个字符串中最大公共子字符串,如"abccade","dgcadde"的最大子串为
"cad"

不同于56的最长公共子串 
DP题算法导论上有：
c[i,j]=0                      i=0||j=0
	  =c[i-1,j-1]+1           a[i]==a[j]
	  =max(c[i-1,j],c[i,j-1]) a[i]!=a[j]	

本题 就是循环枚举 
*/

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;

int GetCommon(char s1[], char s2[])
{
	int len1=strlen(s1);
	int len2=strlen(s2);
	int r,maxlen=0;
	
	for(int i=0;i<len1;i++)
	{
		for(int j=0;j<len2;j++)
		{
			if(s1[i]==s2[j])
			{
				int as=i,bs=j,count=1;
				while(as+1<len1&&bs+1<len2 &&s1[++as]==s2[++bs])
					count++;
				if(count>maxlen)
				{
					maxlen = count;
					r=i;
				}
			}
		}
	}
	for(int i=r;i<r+maxlen;i++)
		printf("%c",s1[i]);
	printf("\n");
	return maxlen;
}
int main()
{
	char a[]={"abccade"};
	char b[]={"dgcadde"};
	printf("%s和%s的最长公共子串是：\n",a,b);
	printf("长度为：%d\n",GetCommon(a,b));
	
	return 0;
}