Regexp finding longest common prefix of two strings

by

If there’s some character that neither string contains —, say, \0 — you could write

"$first\0$second" =~ m/^(.*).*\0\1/s;

and the longest common prefix would be saved as $1.

Edited to add: This is obviously very inefficient. I think that if efficiency is a concern, then this simply isn’t the approach we should be using; but we can at least improve it by changing .* to [^\0]* to prevent useless greediness that will just have to be backtracked again, and wrapping the second [^\0]* in (?>…) to prevent backtracking that can’t help. This:

"$first\0$second" =~ m/^([^\0]*)(?>[^\0]*)\0\1/s;

This will yield the same result, but much more efficiently. (But still not nearly as efficiently as a straightforward non–regex-based approach. If the strings both have length n, I’d expect its worst case to take at least O(n2) time, whereas the straightforward non–regex-based approach would take O(n) time in its worst case.)

Here’s a Python one-liner:

>>> a="stackoverflow"
>>> b = 'stackofpancakes'
>>> a[:[x[0]==x[1] for x in zip(a,b)].index(0)]
0: 'stacko'
>>> a="nothing in"
>>> b = 'common'
>>> a[:[x[0]==x[1] for x in zip(a,b)].index(0)]
1: ''
>>>

More Related Contents:

  1. Convert perl regex to python [closed]
  2. Speed up millions of regex replacements in Python 3
  3. Python string.replace regular expression [duplicate]
  4. How can I remove text within parentheses with a regex?
  5. How to input a regex in string.replace?
  6. How to replace the first occurrence of a regular expression in Python?
  7. Mass string replace in python?
  8. Do Python regular expressions have an equivalent to Ruby’s atomic grouping?
  9. How to use python regex to replace using captured group? [duplicate]
  10. Remove non-ASCII characters from a string using python / django
  11. Searching for IP addresses in a file
  12. Escaping regex string
  13. Fast punctuation removal with pandas
  14. How do you validate a URL with a regular expression in Python?
  15. Regex matching between two strings?
  16. Removing prefix from column names in Pandas
  17. Find USA phone numbers in python script
  18. How to use python-docx to replace text in a Word document and save
  19. Find out how many times a regex matches in a string in Python
  20. How do I specify a range of unicode characters
  21. Regular Expression to match cross platform newline characters
  22. RegExp match repeated characters
  23. Re.sub not working for me
  24. Does Flask support regular expressions in its URL routing?
  25. Regex to find words between two tags
  26. python-pptx – How to replace keyword across multiple runs?
  27. Python – Regular expressions get numbers between parenthesis
  28. Extracting matches with the original case used in the pattern during a case insensitive search
  29. Why doesn’t ignorecase flag (re.I) work in re.sub() [duplicate]
  30. Python replace function [replace once]

Leave a Comment