首页 > 试题广场 >

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

[问答题]
编写函数,获取两段字符串的最长公共子串的长度,例如:
S1= GCCCTAGCCAGDE
S2= GCGCCAGTGDE
这两个序列的最长公共子串是GCCAG,也就是说返回值。
1)请先描述思路;
2)编写完整代码实现,编程语言不限。

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

子串x(ABCBDAB),y(BDCABA)

生成的c数组为(数组c,b皆省略了第一行和第一列ps:全为零)
0 0 0 1 1 1
1 1 1 1 2 2
1 1 2 2 2 2
1 1 2 2 3 3
1 2 2 2 3 3
1 2 2 3 3 4
1 2 2 3 4 4
用来记录路径的数组b(0代表斜上,1代表上,-1代表左边,,即c[i][j]是依赖c[i-1][j-1]或c[i][j-1]或c[i-1][j])
1 1 1 0 -1 0
0 -1 -1 1 0 -1
1 1 0 -1 1 1
0 1 1 1 0 -1
1 0 1 1 1 1
1 1 1 0 1 0
0 1 1 1 0 1
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;
}
编辑于 2017-04-10 12:26:56 回复(0)
#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;
}

发表于 2016-06-16 16:01:49 回复(1)
package niuke.com;
//最长共同字符串
public class LongeSub {

public static void main(String[] args) {
String s1="abcdesqouy";
String s2="desqwsdwe";
System.out.println(subStr(s1,s2));

}
public static String subStr(String s1,String s2){
String s = null;
int flag=0;
//找到更短的字符串!
if(s1.length()>s2.length()){
s=s1;
s1=s2;
s2=s;
}
//如果更短的字符串几个,遍历就有几层,
for(int i=0;i<s1.length();++i){
//第j层有i+1种可能,从长往短找
for(int j=0;j<i+1;++j){
s=s1.substring(j, s1.length()-i+j);
//如果更长的字符串包含当前这个子串,退出循环
if(s2.contains(s)){
//两重循环,设置一个记号,方便一次性退出
flag=1;
break;
}
}
if(flag==1)
break;
}
return s;
}

}
发表于 2016-01-21 22:03:56 回复(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;
}


发表于 2015-08-07 16:11:06 回复(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;
    }
}

发表于 2021-03-13 09:51:02 回复(0)
public static void main(String[] args) {
    String s1 = "GCCCTAGCCAGDE";
        String s2 = "GCGCCAGTGDE";
        String str = s1.length() > s2.length() ? s2 : s1; //短串
        String str2 = s1.length() > s2.length() ? s1 : s2; //长串
        Set<String> set = new HashSet<>();
        for(int i=0;i<str.length();i++){
            String t = str.substring(i, str.length());
            char[] c = t.toCharArray();
            set.addAll(t4_1(c));
        }
        System.out.println("非重复子串:"+set);
        
        List<String> list = new ArrayList<>();
        for(String s : set){
            if(str2.indexOf(s) != -1){
                list.add(s);
            }
        }
        String str3 = "";
        for(String st : list){
            if(st.length() > str3.length()){
                str3 = st;
            }
        }
        System.out.println("最大子串:"+str3);

}
public static Set<String> t4_1(char[] c){
        Set<String> set = new HashSet<>();
        StringBuffer sb = new StringBuffer();
        for(int i=0;i<c.length;i++){
            String[] t = String.valueOf(sb).split(",");
            if(t.length >= 1){
                sb.append(t[t.length-1]);
            }
            sb.append(c[i]).append(",");
        }
        System.out.println("子串:"+sb);
        String[] t = String.valueOf(sb).split(",");
        for(int i=0;i<t.length;i++){
            set.add(t[i]);
        }
        return set;
    }

发表于 2018-03-14 20:52:56 回复(0)
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));
    }
}

发表于 2018-03-04 15:55:06 回复(0)
1.首先以较短的那个字符串为准开始匹配,因为就算全部字符串都能匹配到,那也只可能是最短字符串全部。如果以较多字符串来匹配的话,那么匹配到后,可能还会在后面全匹配到,当然你也可以添加判断条件,一旦匹配到就退出。
2.我们应该以从长到短开始匹配。因为假如有两个字符串,假设最短那个长度是6,当你匹配到两个字符串长度为2相同的时候,可能后面还会匹配到长度为3相同的字符串。反过来,假如你匹配到长度为3相等的时候,你就不必要匹配长度为2相等的了,也就是你一旦找到最大长度的时候,你就不必要最匹配短的了。
3.为避免匹配不到相同字符串出现空指向异常,所以String初始化时赋值空字符串,及 String string = new String("")
JAVA代码如下:
public static void main(String[] args)  {
        String s2= "GCCCTAGCCAGDE";
        String s1= "GCGCCAGTGDE";
        System.out.println(getMaxLength(s1,s2).length());
    }
    public static String getMaxLength(String str1, String str2) {
        boolean flag = false;
        String s1 = str1;
        String s2 = str2;
        String string = new String("");
        if (s1.length() > s2.length()) {
            string = s1;
            s1 = s2;
            s2 = string;
        }
        for (int i = s1.length(); i > 0; i--) {
            for (int n = 0; n<= s1.length() - i; n++) {
                if (s2.contains(s1.substring(n, n + i))) {
                    string = s1.substring(n, n + i);
                    flag = true;
                    break;
                }
            }
            if (flag)
                break;
        }
        return string;
}

发表于 2017-03-21 13:40:38 回复(0)
#include<iostream>
using namespace std;

int lcs(char *str1,char *str2)
{
const int len1 = strlen(str1);
const int len2 = strlen(str2); 
int **buffer = new int*[len1];
for (int i=0;i< len1;i++)
buffer[i]=new int[len2];
int maxLen = 0;
int maxIndexInStr1 = 0;
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
if (str1[i]!=str2[j]) buffer[i][j]=0;
else if(i==0||j==0) buffer[i][j]=1;
else buffer[i][j]=buffer[i-1][j-1]+1;
if(buffer[i][j]>maxLen) 
{  
maxLen=buffer[i][j];
maxIndexInStr1 = i;
   }
}
}
//输出公共字符串
for(int i=maxLen-1;i>=0;i--)cout<<str1[maxIndexInStr1-i];

for(int i=0;i<len1;i++) delete[]buffer[i];
return maxLen;
}


int main()
{
char *str1="GCCCTAGCCAGDE";
char *str2="GCGCCAGTGDE";
int ans = lcs(str1,str2);
system("pause");
return 0;
}

发表于 2015-10-30 10:22:44 回复(0)
string maxchildstr(string s1,string s2)
{
    int len1=s1.size();
    int len2=s2.size();
    string result="";
    if(len1==0||len2==0)
return result;
    int ** k=new int *[len1];
for(int i=0;i<len1;i++)
{
   k[i]=new int[len2];
    memset(k[i],0,sizeof(int)*len2);
}

for(int i=0;i<len1;i++)
{
if(s2[0]==s1[i]) 
k[i][0]=1;
}

for(int j=0;j<len2;j++)
{
if(s2[j]==s1[0]) 
k[0][j]=1;
}

for(int i=1;i<len1;i++)
{
for(int j=1;j<len2;j++)
{
if(s1[i]==s2[j])
k[i][j]=k[i-1][j-1]+1;
}
}
int x=0;
int y=0;
int max=0;

for(int i=0;i<len1;i++)
for(int j=0;j<len2;j++)
{
if(k[i][j]>max)
{
x=i;
y=j;
max=k[i][j];
}
}

if(max>0)
{
for(int i=x-max+1;i<=x;i++)
result+=s1[i];
}
return result;
}
编辑于 2015-09-11 19:51:58 回复(0)
<div> /** </div> <div> 1)建立一个矩阵A,行数为S2的长度,列数为S1的长度,则A[i][j]表示S2的i位和S1的j位字母是否相等,相等为1,否则为0,填满整个矩阵后,寻找从左上到右下最长对角线的长度; </div> <div> 2)将1)中建立的矩阵A压缩成一个数组,长度为S1的长度,则在第j轮遍历时,若S2的i位和S1的j位字母相等,则A[i]=A[i-1]+1,否则A[i]=0; </div> <div> 3)由于每一轮只能检查一个数,事实上可以将2)中建立的矩阵A压缩成一个数,记录下上一轮相等的字母及长度len,当遍历j轮结束后可以得到长度len,这样虽然时间复杂度仍然是O(n^2),但空间复杂度可以降到O(1)。 </div> <div> */ </div> <div> <br /> </div> <div> //按照上面思路的第3种情况来进行代码实现 </div> <div> public class Solution{ </div> <div> &nbsp; &nbsp; public String sameSubstring(String s1, String s2){ </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; if(s1 == null || s2 == null)<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; return null;<br /> </div> <div> <br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; int len1 = s1.length(); </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; int len2 = s2.length();<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; char last = null; int len = 0, max = 0;<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; for(int &nbsp;i = 0; i &lt; len2; i ++){<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; for(int j = 0; j &lt; len1; j ++){<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; if(s1.charAt(j) == s2.charAt(i) &amp;&amp; (last == null || s1.charAt(j - 1) == last)){ </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; last = s1.charAt(j);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; len ++;<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; max = Math.max(len, max);<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; }<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; else{&nbsp;&nbsp;&nbsp;&nbsp;<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; last = null;<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; len = 0;<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; }<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; }<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; }<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; return max;<br /> </div> <div> &nbsp; &nbsp; }<br /> </div> <div> } </div>
发表于 2015-09-11 10:00:38 回复(0)
思路:求串X(i, i+1, i+2....)和串Y(j, j+1, j+2...)的最大的公共子串,即求X和Y的递增增量为1且Xi=Yj, X(i+1)=Y(j+1).....。令C[i][j]表示Xi和Yj的最大子串的长度,则利用动态规划的思路,如果Xi==Yj, C[i][j] = C[i-1][j-1] + 1, 如果Xi != Yj,则C[i][j]=0,最后的LCS= max{  c[i][j],  1<=i<=n, 1<=j<=m}
代码:
#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 

发表于 2015-09-11 09:36:55 回复(1)
 用 DP 算法
 定义一个数组 DP【i】  i表示从短串的第一个开始截取到I,这个子串与长串的最长公共子串长度存在数组中,从第0个开始,每次都做一次判断 以第i为结尾的往前数DP[I-1]次,看这个长度为DP[I-1]+1的串是否为S1的子串。
如果是则DP【i】=DP[I-1]+1 
 否则DP[I]=DP[I-1]
发表于 2015-09-09 16:46:09 回复(0)











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);

}


发表于 2015-09-07 01:16:28 回复(0)
#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
请按任意键继续. . .

发表于 2015-08-29 16:42:40 回复(0)
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]);
			}
		}

	}

发表于 2015-08-11 15:53:17 回复(0)
这道题使用矩阵对角线能够比较形象的描述问题解法,放出自己的C++代码如下:
int longestCommonString(string s1, string s2)
{
  int len = 0;

  int *temp = new int[s2.length()];
  memset(temp, 0, s2.length() * sizeof(int));

  for (int i = 0; i < s1.length(); i++)
  {
   for (int j = s2.length() -1; j >= 0; j--)
   {
     if (s1[i] == s2[j])
    {
      if (i == 0 || j == 0)
        temp[j] = 1;
      else
          temp[j] = temp[j - 1] + 1;

       if (len < temp[j])
         len = temp[j];
     }
  }
  else
    temp[j] = 0;
 }

 return len;
}

发表于 2015-04-02 14:54:00 回复(0)
先将S1拆分成字符串数组,在数组中取字符串与S2对比,当有相同的字符串时做临存,有大的替换临存数据,最后返回的就是最长的字符串
发表于 2015-02-28 18:47:49 回复(0)
逐个比对。
发表于 2014-11-29 13:25:15 回复(0)
xxj头像 xxj
公共子窜问题
使用矩阵对角线原理实现
构造矩阵sizeof(S1)长,sizeof(S2)宽
依次遍历,对应矩阵下标xy中看S1[x]是否等于矩阵下标S2[y]
如果相等,则矩阵xy位置的值为矩阵x-1,y-1下标值(超出为0)加1

最后构造完成后找出其中矩阵中最大的值,xy
然后一次下标对角线回溯到0(可递归或倒序输出)

完成


发表于 2014-11-18 15:55:31 回复(0)