g*******s
发帖数: 2963 | 1 要求和传统用DP的LCS不太一样，只找连续匹配的就行了。 类似与leetcode上那道
Longest Common Prefix的题，但是不一定是prefix。
比如 abcde和aebcd输出的是bcd，（传统的LCS是abcd）
只是两个string的话比传统LCS容易不少，现在问题是输入是n个string，从所有的里面
找出这个common substring。
除了直接把两个string比的方法直接循环扩展，还有什么更好的方法么？ | b*****n
发帖数: 618 | 2 这题是codeeval上的吧
可以用suffix tree做吧 | b******7
发帖数: 92 | 3 f(i,j)表示共同字符以s1的第i+1，s2的第j+1个字符结尾时的长度
f(i,j)= f(i-1,j-1) + 1 if s1[i] == s2[j] else 0
f(0,j) = 1 if s1[0]==s2[j] else 0
f(i,0) = 1 if s1[i] ==s2[0] else 0
统计f(i,j)最大值 | a********n
发帖数: 1287 | 4 用suffix array
char* LongestCommonSubStr( char* a, char* b )
{
if( !a || !b )
{
return NULL;
}
int sizea = strlen( a );
int sizeb = strlen( b );
char** suffix = new char*[sizea + sizeb];
int suffixIdx = 0;
for( int i = 0; i < sizea; i++ )
{
suffix[suffixIdx++] = a + i;
}
for( int i = 0; i < sizeb; i++ )
{
suffix[suffixIdx++] = b + i;
}
std::sort( suffix, suffix + sizea + sizeb, Comp() );
int maxLen = 0;
char* result = new char[sizea + sizeb];
for( int i = 0; i < sizea + sizeb - 1; i++ )
{
char strLocal[MAX];
CommonPrefix( suffix[i], suffix[i+1], strLocal );
if( strlen( strLocal ) > maxLen )
{
strcpy( result, strLocal );
maxLen = strlen( strLocal );
}
}
return result;
} | g*******s
发帖数: 2963 | 5 这个就是传统的LCS简化把。
我问的关键是n个字符串同时比啊。。。。。
就是觉得建一个n维矩阵有点太慢了
string LongestCommonSubStr( vector strs )
【在 b******7 的大作中提到】
: f(i,j)表示共同字符以s1的第i+1，s2的第j+1个字符结尾时的长度
: f(i,j)= f(i-1,j-1) + 1 if s1[i] == s2[j] else 0
: f(0,j) = 1 if s1[0]==s2[j] else 0
: f(i,0) = 1 if s1[i] ==s2[0] else 0
: 统计f(i,j)最大值
|
|
