Skip to content

Instantly share code, notes, and snippets.

@maxfischer2781
Last active January 5, 2020 17:26
Show Gist options
  • Save maxfischer2781/f9040c6d1fe33afeaa5d4274854dd1c9 to your computer and use it in GitHub Desktop.
Save maxfischer2781/f9040c6d1fe33afeaa5d4274854dd1c9 to your computer and use it in GitHub Desktop.
Python string alignment
from itertools import accumulate
a = ['a', '30', '-', 'foot', 'und', 'ete', 'cted']
b = ['a', '30-foot', 'undetected']
def alignment(a: "Iterable[str]", b: "Iterable[str]") -> "List[List[int]]":
if ''.join(a) != ''.join(b):
raise ValueError("a and b must be fragments of the same string")
target_subs = accumulate(b)
next_target = next(target_subs, '')
results, match = [], []
for idx, current in enumerate(accumulate(a)):
match.append(idx)
if current == next_target:
results.append(match)
match = []
next_target = next(target_subs, '')
elif len(current) >= len(next_target):
raise ValueError("a must contain only fragments of b")
return results
print(alignment(a, b))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment