Tuesday, March 22, 2011

most repeat time and longest subsequence

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