CODEWITHSUNDEEP
pythoncdynamic-programminglcs
Erodotos Demetriou
Erodotos Demetriou

Reputation: 73

Longest Common Subsequence C (Python Script explanation)

i have been working for the last few days on a Longest Common Subsequence program, in C, using dynamic programming. Though, I have a memory issue as i am trying to process a lot of data (and i mean A LOT) which result to memory overflow.

Fortunately i have found a linear space complexity algorithm which can be useful not getting memory overflow, but is written in Python. Can someone help me understand what is going on in the picture below?

Python Script for LCS Distance

More specific i don t understand what it going on in line "curr = list(itertools.repeat(0, 1 + ny))"

For the rest i can guess.

Thanks in advance!

Upvotes: 0

Views: 390

Answers (1)

Rahul Agarwal
Rahul Agarwal

Reputation: 4100

This is how it works:

  1. Read length of ys by the code my=len(ys) which will be 10 in the "Chimpanzee" example

  2. your itertools.repeat will be list(itertools.repeat(1,11)) will give you a list with 1 eleven times

    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

And as you said rest you have figured it out.

For more info on repeat check this out:

https://docs.python.org/2/library/itertools.html

Upvotes: 1

Related Questions