My question is simple: Is there an O(n) algorithm for finding the longest contiguous subsequence between two sequences A and B? I searched it, but all the results were about the LCS problem, which is not what I'm seeking.
Note: if you are willing to give any sample code, you are more than welcome to do so, but please, if you can, in C or C++.
Edit: Here is an example:
A: { a, b, a, b, b, b, a }
B: { a, d, b, b, b, c, n }
longest common contiguous subsequence: { b, b, b }
{a,b,c,d,d}
and{d,d,a,b,c}
yields{d,d}
? – Fibrosis