MCS in length L(Maximum consecutive subsequence in length L)

cplusplus · Post by **cplusplus** » Fri Nov 18, 2005 8:06 pm

Hello everyone~

It's easy to solve MCS in O(N) with array of lenth N

here is another similiar question

Find the MCS with length not greater than L in O(N) (not O(NL))

Does anyone the algorithms to solve it?

any information will be great~

Thank you very much~

Monsoon · Post by **Monsoon** » Sat Nov 19, 2005 12:56 am

this is probably that you wish to see:

http://www.csie.ntu.edu.tw/~kmchao/seq04spr/jcss.pdf

cplusplus · Post by **cplusplus** » Sat Nov 19, 2005 8:58 pm

Thank you so much!!

I'd thought an algorithm that similiar to the one proposed in the papaer

but I thought it would be O(N^2) in worst case, don't know it is O(N)

actually by amortized analyze...

Thank your so much!!!!