人家等着你来上床嘛# Joke - 肚皮舞运动
F*r
1 楼
一个字符串，要求返回重复次数最多且最长的子字符串（假设源字符串中最长重复次数
最多的子字符串只有一个）。
例如 “abcabcdfabcdf”要求返回“abcdf”. 因为“
abcdf”重复次数最多且最长。
最多的子字符串只有一个）。
例如 “abcabcdfabcdf”要求返回“abcdf”. 因为“
abcdf”重复次数最多且最长。
C*g
2 楼
h*3
3 楼
这题题目不是很清楚啊。
你的例子里面， abc 重复了3次， abcdf 重复2次，难道不应该返回abc吗？
【在 F**********r 的大作中提到】
: 一个字符串，要求返回重复次数最多且最长的子字符串（假设源字符串中最长重复次数
: 最多的子字符串只有一个）。
: 例如 “abcabcdfabcdf”要求返回“abcdf”. 因为“
: abcdf”重复次数最多且最长。
你的例子里面， abc 重复了3次， abcdf 重复2次，难道不应该返回abc吗？
【在 F**********r 的大作中提到】
: 一个字符串，要求返回重复次数最多且最长的子字符串（假设源字符串中最长重复次数
: 最多的子字符串只有一个）。
: 例如 “abcabcdfabcdf”要求返回“abcdf”. 因为“
: abcdf”重复次数最多且最长。
x*u
4 楼
老了
g*s
5 楼
subsequence是经典的dynamic programming的问题
z*o
6 楼
这个是标准的Suffix Array的 nLogn 吧
z*o
7 楼
先构造后缀：
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的
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
8 楼
汗，没看清楚，以为是subsequence, substring就是suffix tree了
F*r
9 楼
那么这些后缀怎么放比较好呢？就是简单的创造数组的话，直接就O(n^2)了？
【在 z****o 的大作中提到】
: 先构造后缀：
: abcabcdfabcdf
: bcabcdfabcdf
: cabcdfabcdf
: abcdfabcdf
: bcdfabcdf
: cdfabcdf
: dfabcdf
: fabcdf
: abcdf
【在 z****o 的大作中提到】
: 先构造后缀：
: abcabcdfabcdf
: bcabcdfabcdf
: cabcdfabcdf
: abcdfabcdf
: bcdfabcdf
: cdfabcdf
: dfabcdf
: fabcdf
: abcdf
b*8
10 楼
后缀树的确很好，可以强行记住几个结论。但是实际面试中，会问如何构造后缀树吗？
这个就麻烦了。
【在 z****o 的大作中提到】
: 先构造后缀：
: abcabcdfabcdf
: bcabcdfabcdf
: cabcdfabcdf
: abcdfabcdf
: bcdfabcdf
: cdfabcdf
: dfabcdf
: fabcdf
: abcdf
这个就麻烦了。
【在 z****o 的大作中提到】
: 先构造后缀：
: abcabcdfabcdf
: bcabcdfabcdf
: cabcdfabcdf
: abcdfabcdf
: bcdfabcdf
: cdfabcdf
: dfabcdf
: fabcdf
: abcdf
j*x
11 楼
后缀树这种给人写要写一个星期的东西不要总是挂在心上
纯粹是应付面试，么啥意思。。。
纯粹是应付面试，么啥意思。。。
A*i
12 楼
一个trie+遍历次数统计就可以了
h*c
13 楼
如果重复的话，最长子串最长为二分之一，只需比较两个字符，就可以排除二重复，
同理排除三重复，四重复，
后面还没想好。
同理排除三重复，四重复，
后面还没想好。
h*c
14 楼
就排除了最长子串是长度二分之一的可能性，
then save you a lot fo trouble.
【在 h**********c 的大作中提到】
: 如果重复的话，最长子串最长为二分之一，只需比较两个字符，就可以排除二重复，
: 同理排除三重复，四重复，
: 后面还没想好。
then save you a lot fo trouble.
【在 h**********c 的大作中提到】
: 如果重复的话，最长子串最长为二分之一，只需比较两个字符，就可以排除二重复，
: 同理排除三重复，四重复，
: 后面还没想好。
m*q
15 楼
另开一个指针数组，指向原数组中对应的元素，然后对指针数组排序，
其实只是交换指针，空间O(n)。见《编程珠玑》
【在 F**********r 的大作中提到】
: 那么这些后缀怎么放比较好呢？就是简单的创造数组的话，直接就O(n^2)了？
其实只是交换指针，空间O(n)。见《编程珠玑》
【在 F**********r 的大作中提到】
: 那么这些后缀怎么放比较好呢？就是简单的创造数组的话，直接就O(n^2)了？
相关阅读