most repeat time and longest subsequence
--
consturct sufficx:
abcabcdfabcdf
bcabcdfabcdf
cabcdfabcdf
abcdfabcdf
bcdfabcdf
cdfabcdf
dfabcdf
fabcdf
abcdf
bcdf
cdf
df
f
then sort.,compute neighbor string's longest common prefix length
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
longest is :5, Most repeat is : number of long continuously positive value +1 = 3
whole time complexity is O( nLogn)
No comments:
Post a Comment