m******d
发帖数: 414 | 1 之前有人贴出了常见的那个求Maximum repetitive substring的代码，如下：
void MaxDuplicatedSubstring(char *input, char *result)
{
int length = strlen(input);
char **substrings = new char**[length];
for (int i=0; i < length; i++)
substrings[i] = input + i;
qsort(substrings, length, sizeof(char*), (int (*)(const void*, const void*
))strcmp);
int max = 0;
int index = -1;
for (int i=0; i < length - 1; i++)
{
int c = 0;
while (substrings[i][c] && substrings[i+1][c] && substrings[i][c] ==
substrin | i******t
发帖数: 370 | 2
~~~~~~~~~~~~"new char*"?
void*
【在 m******d 的大作中提到】
: 之前有人贴出了常见的那个求Maximum repetitive substring的代码，如下：
: void MaxDuplicatedSubstring(char *input, char *result)
: {
: int length = strlen(input);
: char **substrings = new char**[length];
: for (int i=0; i < length; i++)
: substrings[i] = input + i;
: qsort(substrings, length, sizeof(char*), (int (*)(const void*, const void*
: ))strcmp);
: int max = 0;
| g*******y
发帖数: 1930 | 3 你这个sort，worst case 得有n^2*lgn甚至n^3吧？比如"aaaaaaaaaaaaa"
这个问题应该是用suffix tree是最佳的了, O(n)。
考虑到suffix tree写起来有些困难的话，退而求其次也应该用DP，很简洁的几句话就
能做到O(n^2)了。 | m******d
发帖数: 414 | 4 之前有人贴出了常见的那个求Maximum repetitive substring的代码，如下：
void MaxDuplicatedSubstring(char *input, char *result)
{
int length = strlen(input);
char **substrings = new char**[length];
for (int i=0; i < length; i++)
substrings[i] = input + i;
qsort(substrings, length, sizeof(char*), (int (*)(const void*, const void*
))strcmp);
int max = 0;
int index = -1;
for (int i=0; i < length - 1; i++)
{
int c = 0;
while (substrings[i][c] && substrings[i+1][c] && substrings[i][c] ==
substrings[i+1][c]) c++;
if (c > max) {max = c; index = i;}
}
if (index >= 0)
memmove(result, substrings[index], max);
result[max] = 0;
delete [] substrings;
}
我试了一下，qsort后substrings和排序前的substrings一样。举例：for abcabc：
substrings排序前是{abcabc，bcabc，cabc，abc，bc, c}，排序后还是{abcabc，
bcabc，cabc，abc，bc, c}，而不是预期的{abc，abcabc，bc，bcabc，c，cabc}。
后来我自己写了个简单的冒泡排序代码来排序substrings，并对这个排序结果再运用一
遍qsort，发现还是回到最初的substrings。
难道这个qsort实质的排序对象是字符串地址而不是字符串内容？
谢谢大家赐教。 | i******t
发帖数: 370 | 5
~~~~~~~~~~~~"new char*"?
void*
【在 m******d 的大作中提到】
: 之前有人贴出了常见的那个求Maximum repetitive substring的代码，如下：
: void MaxDuplicatedSubstring(char *input, char *result)
: {
: int length = strlen(input);
: char **substrings = new char**[length];
: for (int i=0; i < length; i++)
: substrings[i] = input + i;
: qsort(substrings, length, sizeof(char*), (int (*)(const void*, const void*
: ))strcmp);
: int max = 0;
| g*******y
发帖数: 1930 | 6 你这个sort，worst case 得有n^2*lgn甚至n^3吧？比如"aaaaaaaaaaaaa"
这个问题应该是用suffix tree是最佳的了, O(n)。
考虑到suffix tree写起来有些困难的话，退而求其次也应该用DP，很简洁的几句话就
能做到O(n^2)了。 | a***r
发帖数: 93 | 7
这题如果用DP来做，哪位给分析一下什么是subproblem？
【在 g*******y 的大作中提到】
: 你这个sort，worst case 得有n^2*lgn甚至n^3吧？比如"aaaaaaaaaaaaa"
: 这个问题应该是用suffix tree是最佳的了, O(n)。
: 考虑到suffix tree写起来有些困难的话，退而求其次也应该用DP，很简洁的几句话就
: 能做到O(n^2)了。
| r*****s
发帖数: 51 | 8 a b c a b c
0 0 0 0 0 0 0
a 0 1 0 0 1 0 0
b 0 0 2 0 0 2 0
c 0 0 0 3 0 0 3
a 0 1 0 0 4 0 0
b 0 0 2 0 0 5 0
c 0 0 0 3 0 0 6
找非对角线上最大的数，即为最长重复序列的长度
【在 a***r 的大作中提到】
:
: 这题如果用DP来做，哪位给分析一下什么是subproblem？
|
|
