I have a string $a_0a_1..a_{n-1}$
Lets say we split the string at pos $i$, so the string are
$a_0a_1....a_{i}$ and $a_{i+1}a_{i+2}....a_{n-1}$
Now I need to compute:
$max(LCS(a_0a_1....a_{i} , a_{i+1}a_{i+2}....a_{n-1}))$ for all $i$ in $[0,n-1]$
common LCS algorithms takes $O(n^2)$ time. so if we use that n times it would be $O(n^3)$. Given that there are many overlapping parts of string can we do better ?
I don't need the subsequence , I just need the max subsequence length and position of splitting.