FilesExpand file tree

 master

/

longest_common_subsequence.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

28 lines (25 loc) · 675 Bytes

 master

/

longest_common_subsequence.py

Copy path

Top

File metadata and controls

• Code
• Blame

28 lines (25 loc) · 675 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

"""

Given string a and b, with b containing all distinct characters,

find the longest common sub sequence's length.

Expected complexity O(n logn).

"""

def max_common_sub_string(s1, s2):

# Assuming s2 has all unique chars

s2dic = {s2[i]: i for i in range(len(s2))}

maxr = 0

subs = ''

i = 0

while i < len(s1):

if s1[i] in s2dic:

j = s2dic[s1[i]]

k = i

while j < len(s2) and k < len(s1) and s1[k] == s2[j]:

k += 1

j += 1

if k - i > maxr:

maxr = k-i

subs = s1[i:k]

i = k

else:

i += 1

return subs