0

I am trying to find a way to get the code to determine the longest length of sequences in common between two sequences.

Example:

So if we had sequence A: 12343241234132142 and sequence B: 231232412431. The answer would be 32412, hence 5 elements in common, if I am not mistaken. Sequence A and B would have different sizes, but one of the sequences would always be the same (sequence A would always have 100 elements).

Previous Research:

I have looked at various ways of doing this: longest common substring, sequence matcher, etc. However, it only gave me the ratio of similarity, which is not informative, as I want to know the number of consecutive sequence elements that are common between sequences.

Andrej Kesely
  • 168,389
  • 15
  • 48
  • 91
CatM
  • 284
  • 2
  • 12
  • `324123` doesn't appear in `B`... – ShadowRanger Jul 27 '19 at 00:20
  • You are right, it is just five elements. You marked this as duplicate of another question but I looked and it did not answer what I asked. Nor was it done with Python. Like I said, I looked at the longest common substring. – CatM Jul 27 '19 at 00:44
  • 1
    I've reopened, but that is basically the answer in *any* language; suffix trees are *the* way to solves this *exact* problem. [Python has a number of suffix tree packages that will do the job](https://stackoverflow.com/a/9347724/364696), you just need to use one of them. – ShadowRanger Jul 27 '19 at 01:03
  • Would this example be enough as a guideline? https://pypi.org/project/suffix-trees/ Sorry for asking so many questions but it is my first time hearing about sufix trees. – CatM Jul 27 '19 at 01:09
  • Even though it looks like it would give me the output I want, I am unable to install the module. – CatM Jul 27 '19 at 01:28
  • 2
    Possible duplicate of [Find common substring between two strings](https://stackoverflow.com/questions/18715688/find-common-substring-between-two-strings), but note the accepted answer is wrong – wjandrea Jul 27 '19 at 01:30
  • Thank you so very much wjandrea! it worked for me! Best wishes. I had looked at sequenceMatcher but did not find this function. Should I remove the question as it does seem to be a duplicate of that one? – CatM Jul 27 '19 at 01:49
  • @CatM Most useful thing to do is answer your own question and then mark your answer as correct. This ensures that if anyone stumbles upon this via Google they are informed (write it as though you were writing for your past self -- include code, reasoning, etc.) – felipe Jul 27 '19 at 06:04
  • @CatM You could just let this question be closed as a duplicate, or do it yourself if you have the option. It may be useful as a signpost to others who have the same question as you. – wjandrea Jul 27 '19 at 13:53

0 Answers0