编写函数，获取两段字符串的最长公共子串的长度，例如： S1

使用动态规划，参考算法导论中所写。

子串x（ABCBDAB）,y（BDCABA）

public int LCS_LENGTH(String x,String y){ int m=x.length(),n=y.length();
    nt b[][]=new int[m+1][n+1];
    int c[][]=new int[m+1][n+1];
    Vector<Character> res= new
    Vector<Character>();
    for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++)
        if(x.charAt(i-1)==y.charAt(j-1)){
            c[i][j]=c[i-1][j-1]+1;
            b[i][j]=0; }
        else if(c[i-1][j]>=c[i][j-1]){
            c[i][j]=c[i-1][j];
            b[i][j]=1;
        }
        else {
            c[i][j]=c[i][j-1];
            b[i][j]=-1;
        }
    }
    int i=m,j=n;
    while(i!=0&&j!=0){//根据b来寻找最大子序列的路径
        if(b[i][j]==0){
            res.add(0,x.charAt(i-1));
            i--;
            j--;
        }else if(b[i][j]==-1){
            j--;
        }else
            i--;
        }
    return res;
}

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
//返回最长公共字符串函数的实现
//采用动态规划算法
int LargestSubstring(string s1,string s2){
    int len1=s1.size();
    int len2=s2.size(); 
    int **c= new int*[len1+1];
    for(int i=0;i<len1+1;i++){
        c[i]=new int[len2+1];
    }    
    memset(&c[0][0],0,(n1+1)*(n2+1));
    int maxnum=-1;
    int endi=0,endj=0;
    for(int i=1;i<len1+1;i++){
        for(int j=1;j<len2+1;j++)
        {
            if(s1[i-1]==s2[j-1]){
                c[i][j]=c[i-1][j-1]+1;
            }else{
                c[i][j]=0;        
            }                                
            if(c[i][j]>maxnum){
                maxnum=c[i][j];
                endi=i;
                endj=j;
            }
        }
    }
    int num=0;        
    for(;endi>=0&&endj>=0&&s[endi]!=s[endj];endi--,endj--){
        num++; 
   }    
   return num;
}
int main(){
     string s1="GCCCTAGCCAGDE" ;
     string s2="GCGCCAGTGDE" ;
     int maxlen=LargestSubsting(s1,s2);
     cout<<"maxlen:"<<maxlen<<endl;    
     return 0;
}

#include<stdio.h>
#include<string.h>
#define N 100
 
//LCS问题：即求两个字符串最长公共子串的问题，这里返回了公共字串，如果只求最长公共字串长度的话，之后有个简单的程序，其实就是里面的一部分
char *LCS(char *a,char *b) 
{
int len_a = strlen(a);  //获取字串的长度 
int len_b = strlen(b);
char *p;
int c[N][N] = {0};      //矩阵c记录两串的匹配情况 
int start,end,len,i,j;  //start表明最长公共子串的起始点，end表明最长公共子串的终止点 
end = len = 0;          //len表明最长公共子串的长度 
for(i=0;i<len_a;i++)    //串开始从前向后比较 
{
for(j=0;j<len_b;j++)
{
if(a[i] == b[j])
if(i == 0 || j == 0)
c[i][j] = 1;
else
c[i][j] = c[i-1][j-1] + 1;
if(c[i][j] > len)
{
len = c[i][j];
end = j;
}
}
}
start = end - len + 1;
p = (char *)malloc(len+1); //数组p记录最长公共子串 
for(i=start;i<=end;i++)
p[i-start] = b[i];
p[len] = '\0';
for(j=0;j<len_b;j++)
{
for(i=0;i<len_a;i++)
printf("%2d",c[i][j]); 
printf("\n");
}
return p;
}
int main(int argc,char *argv[])
{
char str1[N],str2[N];
printf("请输入字符串1：");
gets(str1);
printf("请输入字符串2：");
gets(str2);
printf("最长子串为：%s\n",LCS(str1,str2));
return 0;
}

package 最长公共子串;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        String s1= "GCCCTAGCCAGDE";
        String s2= "GCGCCAGTGDE";
        String maxStr = main.searchForCommonStr(s1, s2);
        System.out.println("最长公共子串为"+maxStr);
    }

    /**
     * maxStr用于记录最大公共子字符串
     * maxLength用于记录最大公共子字符串的长度
     * 从下标为0开始，依次截取起始下标为0的s1的子字符串substring
     * 依次与s2匹配有无公共字符串substring
     * 若有，且substring的长度大于maxLength，则maxLength = substring.length(); maxStr = substring;
     * 否则，继续循环
     * */
    public String searchForCommonStr(String s1, String s2) {
        String maxStr = "";
        int maxLength = 0;

        for (int start = 0; start < s1.length(); start++) {
            for (int end = start + 1; end < s1.length(); end++) {

                String substring = s1.substring(start, end);
                if (s2.indexOf(substring) != -1) {
                    if (substring.length() > maxLength) {
                        maxLength = substring.length();
                        maxStr = substring;
                    }
                }

            }
        }
        return maxStr;
    }
}

package meituan.longestSubString;

/**
 * @author XieLongZhen
 * @time 2018/3/4 14:37
 */
public class LongestSubString {

    /**
     * 由于最长公共子串只可能是最短字符串全部
     * 所以以较短的那个字符串为准从长到短开始匹配
     * 匹配到的就是找到最长公共子串
     */

    public static String getLongestSubString(String s1, String s2) {
        String sub;
        String longer = s1, shorter = s2;
        // 比较长度
        if (longer.length() < shorter.length()) {
            longer = s2;
            shorter = s1;
        }
        // 用更短的字符串匹配
        for (int i = shorter.length(); i > 0; i--) {
            for (int j = 0; j < shorter.length()-i+1; j++) {
                sub = shorter.substring(j, j + i);
                if (longer.contains(sub)){
                    return sub;
                }
            }
        }
        //没有匹配的子串，返回空字符串
        return "";
    }

    public static void main(String[] args) {
        String str1 = "GCCCTAGCCAGDE";
        String str2 = "GCGCCAGTGDE";
        System.out.println(getLongestSubString(str1, str2));
    }
}

}

#if 1
//最长公共子串问题
int LCS(char* str1, char* str2)
{
	if (str1==NULL || str2==NULL)
	{
		return 0;
	}

	int len1 = strlen(str1);
	int len2 = strlen(str2);

	//构造一个大小为len1*len2的二维数组
	int i, j;
	static int** c = new int*[len1+1]; //利用静态变量默认初始化为0的特性
	for (i=0; i<len1+1; i++)
	{
		c[i] = new int[len2 +1];
	}
	
	int x,y;
	int lenLcs = -1;
	for (i=1; i<len1+1; i++)
	{
		for (j=1; j<len2+1; j++)
		{
			if (str1[i-1] == str2[j-1])
			{
				c[i][j] = c[i-1][j-1] + 1;
			}
			else
			{
				c[i][j] = 0;
			}

			if (c[i][j] > lenLcs)
			{
				lenLcs = c[i][j];
				x = i;
				y = j;
			}
		}
	}

	//输出公共子串
	char s[1000];
	int k = lenLcs;
	i = x-1;
	j = y-1;
	s[k--] = '\0';
	while (i>=0 && j>=0)
	{
		if (str1[i] == str2[j])
		{
			s[k--] = str1[i];
			i--;
			j--;
		}
		else
			break;
	}

	cout << "最长公共子串为： ";
	puts(s);

	//释放动态产生的内存
	for (i=0; i<len1+1; i++)
	{
		delete[] c[i];
	}
	delete[] c;

	return lenLcs;
}

#endif 

	  public String getMaxSubString(String s1, String s2)



	   {



	    if(s1==null||s2==null)return null;



	    String temp;



	    if (s1.length() < s2.length())



	     {



	      temp = s2;



	      s2 = s1;



	      s1 = temp;



	     }



	    int len = s2.length();



	    int pos = 0, num = 0;



	    for (int i = 0; i < len; i++)



	     {



	      for (int j = i; j < len - 1; j++)



	       {



	        if (s1.contains(s2.subSequence(i, j)))



	         {



	          if(j-i>num)



	           {



	            num=j-i;



	            pos=i;



	           }



	         }



	        else 



	         break;



	       }



	      if(num>len-i)break;



	     }



	    return s2.substring(pos,num+pos);



	   }

#include <iostream>
#include <string>
using namespace std;
string findSubstr(string &s1, string &s2)
{
	string shorts ,longs;
	string temp;
	if(s1.length() > s2.length())
	{
		shorts = s2;
		longs = s1;
	}
	else 
	{
		shorts = s1;
		longs = s2;
	}
	for(int i = shorts.length() - 1; i > 1; i--)
	{
		for(int j = 0; j < shorts.length(); j++)
		{
			if(i + j < shorts.length())
			{
				temp = shorts.substr(j,i);
				if(longs.find(temp) != string::npos)
					return temp;
			}
		}
	}
	return "";
}
int main()
{
	string str1 = "GCCCTAGCCAGDE";
	string str2 = "GCGCCAGTGDE";
	cout << findSubstr(str1, str2) << endl;

	return 0;
}
GCCAG
请按任意键继续. . .

public static void main(String[] args) {
		
		char[] str1={'g','c','c','c','t','a','g','c','c','a','g','d','e'};
		char[] str2={'g','c','g','c','c','a','g','t','g','d','e'};
		
		int[][] R=new int[str1.length][str2.length];
		int i,j,tmpI,tmpJ;
		int count=0,tmpCount=0;
		int begin=-1,tmpBegin=-1;
		
		for(i=0;i<str1.length;i++)
		{
			for(j=0;j<str2.length;j++)
			{
				if(str1[i]==str2[j])
				{
					R[i][j]=1;
				}
				else
				{
					R[i][j]=0;
				}
			}
		}
		for(i=0;i<str1.length;i++)
		{
			for(j=0;j<str2.length;j++)
			{
				
				if(R[i][j]==1)
				{
					tmpI=i+1;
					tmpJ=j+1;
					tmpCount=1;
					tmpBegin=i;
					if(tmpI<=str1.length-1 && tmpJ<=str2.length-1)
					{
						while(R[tmpI][tmpJ]==1 )
						{
							tmpCount++;
							tmpI=tmpI+1;
							tmpJ=tmpJ+1;
							if(tmpI>str1.length-1 || tmpJ>str2.length-1)
							{
								break;
							}
						}
					}
					if(tmpCount>count)
					{
						count=tmpCount;
						begin=tmpBegin;
					}
				}
			}
		}
		
		if(count>0)
		{
			for(i=begin,j=0;j<count;j++,i++)
			{
				System.out.print(str1[i]);
			}
		}

	}