请教一个字符串比较排序的问题 (转载)# JobHunting - 待字闺中
a*r
1 楼
这题如果用DP来做，哪位给分析一下什么是subproblem？
【 以下文字转载自 Programming 讨论区 】
发信人: minisand (老婆是A+海博), 信区: Programming
标 题: 请教一个字符串比较排序的问题
发信站: BBS 未名空间站 (Mon Nov 9 16:35:46 2009, 美东)
之前有人贴出了常见的那个求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实质的排序对象是字符串地址而不是字符串内容？
谢谢大家赐教。
【 以下文字转载自 Programming 讨论区 】
发信人: minisand (老婆是A+海博), 信区: Programming
标 题: 请教一个字符串比较排序的问题
发信站: BBS 未名空间站 (Mon Nov 9 16:35:46 2009, 美东)
之前有人贴出了常见的那个求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实质的排序对象是字符串地址而不是字符串内容？
谢谢大家赐教。
