首页 > 试题广场 >

找出最长连续字母序列的长度。

[问答题]

给定一个query和一个text，均由小写字母组成。要求在text中找出以同样的顺序连续出现在query中的最长连续字母序列的长度。例如， query为“acbac”，text为“acaccbabb”，那么text中的“cba”为最长的连续出现在query中的字母序列，因此，返回结果应该为其长度3。请注意程序效率。

WilliamJM520

这是最长公共子序列问题。

设A= “a0 ，a1 ，…，am-1”，B= “b0 ，b1 ，…，bm-1”，并Z= “z0 ，z1 ，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：

（1 ）如果am-1=bn-1 ，则zk-1=am-1=bn-1 ，且“z0 ，z1 ，…，zk-2”是“a0 ，a1 ，…，am-2”和“b0 ，b1 ，…，bn-2”的一个最长公共子序列；

（2 ）如果am-1!=bn-1 ，则若zk-1!=am-1 ，蕴涵“z0 ，z1 ，…，zk-1”是“a0 ，a1 ，…，am-2”和“b0 ，b1 ，…，bn-1”的一个最长公共子序列；

（3 ）如果am-1!=bn-1 ，则若zk-1!=bn-1 ，蕴涵“z0 ，z1 ，…，zk-1”是“a0 ，a1 ，…，am-1”和“b0 ，b1 ，…，bn-2”的一个最长公共子序列。

这样，在找A 和B 的公共子序列时，如有am-1=bn-1 ，则进一步解决一个子问题，找“a0 ，a1 ，…，am-2”和“b0 ，b1 ，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1 ，则要解决两个子问题，找出“a0 ，a1 ，…，am-2”和“b0 ，b1 ，…，bn-1”的一个最长公共子序列和找出“a0 ，a1 ，…，am-1”和“b0 ，b1 ，…，bn-2”的一个最长公共子序列，再取两者中较***作为A 和B 的最长公共子序列。

求解：

引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j] 的LCS 的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。
我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i] = Y[j]还是X[i] != Y[j]，就可以计算出c[i][j]。

问题的递归式写成：

回溯输出最长公共子序列过程：

算法分析：
由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m + n)。

代码：

#include < stdio.h >
#include < string .h >
#define MAXLEN 100
void LCSLength( char * x, char * y, int m, int n, int c[][MAXLEN], int b[][MAXLEN]) {
   int i, j;
   for (i = 0 ; i <= m; i ++ )
c[i][ 0 ] = 0 ;
   for (j = 1 ; j <= n; j ++ )
c[ 0 ][j] = 0 ;
   for (i = 1 ; i <= m; i ++ ) {
   for (j = 1 ; j <= n; j ++ ) {
   if (x[i - 1 ] == y[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 ;
}
}
}
}

void PrintLCS( int b[][MAXLEN], char * x, int i, int j) {
   if (i == 0 || j == 0 )
   return ;
   if (b[i][j] == 0 ) {
PrintLCS(b, x, i - 1 , j - 1 );
printf( " %c " , x[i - 1 ]);
}
   else if (b[i][j] == 1 )
PrintLCS(b, x, i - 1 , j);
   else
PrintLCS(b, x, i, j - 1 );
}

int main( int argc, char ** argv) {
   char x[MAXLEN] = { " ABCBDAB " } ;
   char y[MAXLEN] = { " BDCABA " } ;
   int b[MAXLEN][MAXLEN];
   int c[MAXLEN][MAXLEN];
   int m, n;
m = strlen(x);
n = strlen(y);

LCSLength(x, y, m, n, c, b);
PrintLCS(b, x, m, n);
   return 0 ;
}

发表于 2015-03-29 19:14:04 回复(2)

黄玉

#include <iostream>
#include <string>
using namespace std;

int f(string s1,string s2)
{
	int len1=s1.size();
	int max_length=0;

	for( int i=0;i<len1-1;i++)
		for( int j=i+1;j<len1;j++)
		{
		string s=s1.substr(i,j-i+1);
		int index=s2.find(s);
		if(index!=-1) 
		{
		//cout<<s<<endl; 
		if( s.size()>max_length )	max_length=s.size();
		}		
		}
	
	return max_length;
}
int main()
{
    string s1="acbac";
	string s2="acaccbabb";
	cout<<f(s1,s2);
    return 0;
}

编辑于 2015-09-27 18:40:07 回复(0)

我是一块努力的肉

#include<string>

#include<iostream>

using namespace std;

int main()

{

string query;

string text;

cin>>query>>text;

int len1=query.size();

int len2=text.size();

int i,j,k;

int maxlen=0,premaxlen=0;

string temp,result;

for(i=0;i<len1;i++)

{

//maxlen=0;

for(k=len1-i;k>0;k--)

{

temp=query.substr(i,k);

int pos=text.find(temp);

if(pos!=string::npos)

{

if(temp.size()>premaxlen)

{

premaxlen=temp.size();

result.assign(temp);

break;

}

cout<<premaxlen<<"对应的字符串为："<<result<<endl;

return 0;

}

发表于 2015-08-14 20:28:53 回复(1)

阿衰

 public String getCommonSubSeq(String str1, String str2) {
     char[] array1 = str1.toCharArray();
     char[] array2 = str2.toCharArray();
     int max = 0,x = 0,y = 0;
     int length1 = array1.length;
     int length2 = array2.length;
 
     int[][] array = new int[length1+1][length2+1];
 
     for( int i = 0; i < length1; i++ ){
         for( int j = 0; j < length2; j++ ){
             if( array1[i] == array2[j] ){
                 array[i+1][j+1] = array[i][j] + 1;
                 if( array[i+1][j+1] > max ){
                     max = array[i+1][j+1];
                     x = i;
                     y = j;
                 }
             } else {
                 array[i+1][j+1] = 0;
             }
         }
     }
 
     StringBuilder mSB = new StringBuilder();
     for( int i = max - 1; i >= 0; i-- ){
         mSB.append(array1[x-i]);
     }
     return mSB.toString();
 }

发表于 2015-04-02 10:56:32 回复(0)

木上有水

int find(string &text,string &query)

{

int len1,len2;

int count=1;

string t;

len1=text.length();

len2=text.length();

for(int i=len-1;i>1;i--)

{

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

t=text.substr(j,i);

if(query.find(t))

if(t.length()>count)

count=t.length();

}

return count;

}

发表于 2015-03-29 21:30:50 回复(0)

牛克呆

马克

发表于 2015-08-20 18:51:13 回复(0)

无心浪子

public static void find(String str,String str1){
          String str2 = "";
          int i = 0;
          if (str.length()>str1.length()) {
                i = str1.length();
                while (i>0) {
                    if(str.contains(str1.substring(0, i))){
                        str2 = str1.substring(0, i);
                        break;
                    }
                    i--;
                }
            } else {
                i = str.length();
                while (i>0) {
                    if(str1.contains(str.substring(0, i))){
                        str2 = str.substring(0, i);
                        break;
                    }
                    i--;
                }
            }
          System.out.println(str2);
          System.out.println(str2.length());
     }

     public static void main(String args[]){
             find("abcddefghijk","cdasdlkjalksjdljlfjlkasjdabc");
     }

发表于 2015-04-28 14:40:12 回复(0)

牛客733423号

//输入

int n,m；

char s[MAX],t[MAX];

int dp[MAX+1][MAX+1];//dp数组

int solve()

{

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

{

for(int j =0; j<m; j++)

{

if(s[i] == t[j])

{

dp[i+1][j+1] = dp[i][j]+1;

}

esle

{

dp[i+1][j+1] = max(dp[i][j-1],dp[i+1][j]);

}

return dp[n][m];

}

发表于 2015-04-20 00:39:35 回复(0)

提交观点

问题信息

动态规划阿里巴巴

上传者：小牧魔法袋

难度：

8条回答 124收藏 13202浏览

找出最长连续字母序列的长度。

问题信息

热门推荐

相关试题