Tuesday, February 14, 2012

Common sequences in two strings [closed]

I am looking to find all common sequences of works between two strings. For example:

String A: A, B, 1, 2, 3, 4, 5, X

String B: 1, 2, 3, 4, A, B, C

The common sequences here would be A, B & 1, 2, 3, 4

I am looking for a Java solution which will do this.

Thank you very much

1 comment:

  1. It should be something simple, like this for example:

    search for B[i] in A. if it is found, go to 2 and assume j to be index for which B[i] == A[j]. else, repeat this step for i+1 (if B[i+1] exists)
    check if B[i+1] exists. if it does, go to 3. else, finish the algorithm.
    check if B[i+1] equals A[j+1]. repeat this step as long as it does. remember that every iteration is also a different common sequence

    It may not be everything, but it's a good place to start.