F**********r
发帖数: 237 | 1 一个字符串，要求返回重复次数最多且最长的子字符串（假设源字符串中最长重复次数
最多的子字符串只有一个）。
例如 “abcabcdfabcdf”要求返回“abcdf”. 因为“
abcdf”重复次数最多且最长。 |
h*********3
发帖数: 111 | 2 这题题目不是很清楚啊。
你的例子里面， abc 重复了3次， abcdf 重复2次，难道不应该返回abc吗？
【在 F**********r 的大作中提到】
: 一个字符串，要求返回重复次数最多且最长的子字符串（假设源字符串中最长重复次数
: 最多的子字符串只有一个）。
: 例如 “abcabcdfabcdf”要求返回“abcdf”. 因为“
: abcdf”重复次数最多且最长。
|
g*******s
发帖数: 490 | 3 subsequence是经典的dynamic programming的问题 |
z****o
发帖数: 78 | 4 这个是标准的Suffix Array的 nLogn 吧 |
z****o
发帖数: 78 | 5 先构造后缀：
abcabcdfabcdf
bcabcdfabcdf
cabcdfabcdf
abcdfabcdf
bcdfabcdf
cdfabcdf
dfabcdf
fabcdf
abcdf
bcdf
cdf
df
f
之后排序,并且计算相邻string的longest common prefix长度：
0 abcabcdfabcdf
3 abcdf
5 abcdfabcdf
0 bcabcdfabcdf
2 bcdf
4 bcdfabcdf
0 cabcdfabcdf
1 cdf
3 cdfabcdf
0 df
2 dfabcdf
0 f
1 fabcdf
然后要最长的就是那个 5， 最多的就是连续正数的最大长度+1 = 3
整个计算过程是 nLogn的 |
g*******s
发帖数: 490 | 6 汗，没看清楚，以为是subsequence, substring就是suffix tree了 |
F**********r
发帖数: 237 | 7 那么这些后缀怎么放比较好呢？就是简单的创造数组的话，直接就O(n^2)了？
【在 z****o 的大作中提到】
: 先构造后缀：
: abcabcdfabcdf
: bcabcdfabcdf
: cabcdfabcdf
: abcdfabcdf
: bcdfabcdf
: cdfabcdf
: dfabcdf
: fabcdf
: abcdf
|
b*******8
发帖数: 37364 | 8 后缀树的确很好，可以强行记住几个结论。但是实际面试中，会问如何构造后缀树吗？
这个就麻烦了。
【在 z****o 的大作中提到】
: 先构造后缀：
: abcabcdfabcdf
: bcabcdfabcdf
: cabcdfabcdf
: abcdfabcdf
: bcdfabcdf
: cdfabcdf
: dfabcdf
: fabcdf
: abcdf
|
|
j********x
发帖数: 2330 | 9 后缀树这种给人写要写一个星期的东西不要总是挂在心上
纯粹是应付面试，么啥意思。。。 |
A*****i
发帖数: 3587 | |
h**********c
发帖数: 4120 | 11 如果重复的话，最长子串最长为二分之一，只需比较两个字符，就可以排除二重复，
同理排除三重复，四重复，
后面还没想好。 |
h**********c
发帖数: 4120 | 12 就排除了最长子串是长度二分之一的可能性，
then save you a lot fo trouble.
【在 h**********c 的大作中提到】
: 如果重复的话，最长子串最长为二分之一，只需比较两个字符，就可以排除二重复，
: 同理排除三重复，四重复，
: 后面还没想好。
|
m**q
发帖数: 189 | 13 另开一个指针数组，指向原数组中对应的元素，然后对指针数组排序，
其实只是交换指针，空间O(n)。见《编程珠玑》
【在 F**********r 的大作中提到】
: 那么这些后缀怎么放比较好呢？就是简单的创造数组的话，直接就O(n^2)了？
|
