t*****n
发帖数: 167 | 1 给定两个字符串A和B
找出他们最长的公共子串，要求给出算法，考虑两种情况
（1）这个子串必须是连续的（即在A或B中必须连续）
（2）这个子串可以是任意的（即在A或B可以不连续）
我知道第二种情况肯定要用dynamic programming,能在O(|A|*|B|)算出结果。 问题第
一种情况，能否不用dynamic programming， 有什么直接的算法吗？
谢谢！ | d****2
发帖数: 109 | 2 KMP?, what is the temporal complex requirment | t*****n
发帖数: 167 | 3 刚才用C++写了程序，没用STL，简单测试了一下，应该是对的，放上来攒点人品吧，程
序写的有乱，没优化，如果牛人能帮着优化以下就最好了
bool longestCommonString(char *source, char *destination, char *result)
{
if ((source == NULL) || (destination == NULL)) return false;
int m, n, i, j, k;
int start = -1, end = -1;
int length = 0;
char temp;
m = strlen(source);
n = strlen(destination);
int** tempResult = new int*[m];
for (i=0; i
int** tempFlag = new int*[m];
for (i=0; i
for (i=0; i
for
【在 t*****n 的大作中提到】
: 给定两个字符串A和B
: 找出他们最长的公共子串，要求给出算法，考虑两种情况
: （1）这个子串必须是连续的（即在A或B中必须连续）
: （2）这个子串可以是任意的（即在A或B可以不连续）
: 我知道第二种情况肯定要用dynamic programming,能在O(|A|*|B|)算出结果。 问题第
: 一种情况，能否不用dynamic programming， 有什么直接的算法吗？
: 谢谢！
| J*****n
发帖数: 4859 | | d*****r
发帖数: 2583 | 5 wokao...
你们都很牛。。
【在 t*****n 的大作中提到】
: 刚才用C++写了程序，没用STL，简单测试了一下，应该是对的，放上来攒点人品吧，程
: 序写的有乱，没优化，如果牛人能帮着优化以下就最好了
: bool longestCommonString(char *source, char *destination, char *result)
: {
: if ((source == NULL) || (destination == NULL)) return false;
: int m, n, i, j, k;
: int start = -1, end = -1;
: int length = 0;
: char temp;
: m = strlen(source);
| k*******g
发帖数: 263 | | w*****e
发帖数: 197 | 7 两个问题都可以用DP来解
只不过赋值过程稍有区别
但是都是n*n
对于连续的情况可能会有类似KMP的解法
【在 t*****n 的大作中提到】
: 给定两个字符串A和B
: 找出他们最长的公共子串，要求给出算法，考虑两种情况
: （1）这个子串必须是连续的（即在A或B中必须连续）
: （2）这个子串可以是任意的（即在A或B可以不连续）
: 我知道第二种情况肯定要用dynamic programming,能在O(|A|*|B|)算出结果。 问题第
: 一种情况，能否不用dynamic programming， 有什么直接的算法吗？
: 谢谢！
| k*******g
发帖数: 263 | 8 楼主说的dynamic progrmaming跟优化里的dynamic programming有啥区别？ |
|
