人家等着你来上床嘛# Joke - 肚皮舞运动F*r2010-12-16 08:121 楼一个字符串,要求返回重复次数最多且最长的子字符串(假设源字符串中最长重复次数最多的子字符串只有一个)。例如 “abcabcdfabcdf”要求返回“abcdf”. 因为“abcdf”重复次数最多且最长。
h*32010-12-16 08:123 楼 这题题目不是很清楚啊。你的例子里面, abc 重复了3次, abcdf 重复2次,难道不应该返回abc吗?【在 F**********r 的大作中提到】: 一个字符串,要求返回重复次数最多且最长的子字符串(假设源字符串中最长重复次数: 最多的子字符串只有一个)。: 例如 “abcabcdfabcdf”要求返回“abcdf”. 因为“: abcdf”重复次数最多且最长。
z*o2010-12-16 08:127 楼先构造后缀:abcabcdfabcdfbcabcdfabcdfcabcdfabcdfabcdfabcdfbcdfabcdfcdfabcdfdfabcdffabcdfabcdfbcdfcdfdff之后排序,并且计算相邻string的longest common prefix长度:0 abcabcdfabcdf 3 abcdf5 abcdfabcdf0 bcabcdfabcdf2 bcdf4 bcdfabcdf0 cabcdfabcdf1 cdf3 cdfabcdf0 df2 dfabcdf0 f1 fabcdf然后要最长的就是那个 5, 最多的就是连续正数的最大长度+1 = 3整个计算过程是 nLogn的
F*r2010-12-16 08:129 楼那么这些后缀怎么放比较好呢?就是简单的创造数组的话,直接就O(n^2)了?【在 z****o 的大作中提到】: 先构造后缀:: abcabcdfabcdf: bcabcdfabcdf: cabcdfabcdf: abcdfabcdf: bcdfabcdf: cdfabcdf: dfabcdf: fabcdf: abcdf
b*82010-12-16 08:1210 楼后缀树的确很好,可以强行记住几个结论。但是实际面试中,会问如何构造后缀树吗?这个就麻烦了。【在 z****o 的大作中提到】: 先构造后缀:: abcabcdfabcdf: bcabcdfabcdf: cabcdfabcdf: abcdfabcdf: bcdfabcdf: cdfabcdf: dfabcdf: fabcdf: abcdf
h*c2010-12-16 08:1214 楼就排除了最长子串是长度二分之一的可能性,then save you a lot fo trouble.【在 h**********c 的大作中提到】: 如果重复的话,最长子串最长为二分之一,只需比较两个字符,就可以排除二重复,: 同理排除三重复,四重复,: 后面还没想好。
m*q2010-12-16 08:1215 楼另开一个指针数组,指向原数组中对应的元素,然后对指针数组排序,其实只是交换指针,空间O(n)。见《编程珠玑》【在 F**********r 的大作中提到】: 那么这些后缀怎么放比较好呢?就是简单的创造数组的话,直接就O(n^2)了?