I have written a piece of code that finds common patterns in two strings. These patterns have to be in the same order, so for example "I am a person" and "A person I am" would only match "person". The code is crude, all characters, including whitespace and punctuation marks, receive the same treatment. The longest patterns are matched first.
The main function then returns two lists (one per string) of tuples with two elements. The first element is 1 if a substring has been matched, else 0. The second element is the substring.
So the format of returned lists will be like this:
[(1, 'I '), (0, 'am a person\n')] [(1, 'I '), (0, 'can see\n')]
Now to the question -- what do you think about my code? I somehow feel that it's not quite top-notch, and I'm not an experienced coder. Any suggestions on coding style or the algorithms? I hope the code is reasonably clear.
find_raw_patterns function returns lists with alternating integers and strings, so the only thing
find_common_patterns does in addition to calling
find_raw_patterns, is to arrange the lists' elements in two-element-tuples.
longest_common_substring is copied directly from Wikibooks, and I'm not very concerned about that function.
def longest_common_substring(S1, S2): M = [*(1+len(S2)) for i in range(1+len(S1))] longest, x_longest = 0, 0 for x in range(1,1+len(S1)): for y in range(1,1+len(S2)): if S1[x-1] == S2[y-1]: M[x][y] = M[x-1][y-1] + 1 if M[x][y]>longest: longest = M[x][y] x_longest = x else: M[x][y] = 0 return S1[x_longest-longest: x_longest] def find_common_patterns(s1, s2): arranged1 =  arranged2 =  (ptr1, ptr2) = find_raw_patterns(s1, s2) #ptr - pattern for i in range(len(ptr1) - 1): if type(ptr1[i]) == int: arranged1.append((ptr1[i], ptr1[i+1])) for i in range(len(ptr2) - 1): if type(ptr2[i]) == int: arranged2.append((ptr2[i], ptr2[i+1])) return (arranged1, arranged2) def find_raw_patterns(s1, s2): # used recursively one =  # used to reassemble strings, but with patterns and integer showing whether it's been matched or not two =  # same, but for the second string com = longest_common_substring(s1, s2) if len(com) < 2: return ((0, s1), (0, s2)) elif len(com) >= 2: i1 = s1.index(com) i2 = s2.index(com) s1_bef = s1[:i1] #part of string before the matched pattern s1_aft = s1[i1 + len(com) : ] # -//- after matched pattern s2_bef = s2[:i2] s2_aft = s2[i2 + len(com) : ] if len(s1_bef) > 0 and len(s2_bef) > 0: # find patterns in first parts of strings res = find_raw_patterns(s1_bef, s2_bef) one.extend(res) two.extend(res) one.extend((1, com)) # add current pattern two.extend((1, com)) if len(s1_aft) > 0 and len(s2_aft) > 0: # find patterns from second parts res = find_raw_patterns(s1_aft, s2_aft) one.extend(res) two.extend(res) return (one, two)