Get all possible strings between 2 substrings in Python

user_1390723 0
Viewed 95

The question of getting an in-between string has been asked before but does not cover certain conditions. In my case, I may have a string like the following:

subject = '"lorem ipsum", "foo", "baz", "bar", "lorem ipsum", "bar", "ipsum", "foo", "baz", "bar"'

I want to extract all instances of text between foo", " and ", "bar". The traditional "Get between" answer is:

import re
result = re.findall('foo", "(.*)", "bar', subject)
print(result)

which returns only 1 result string:

'baz", "bar", "lorem ipsum", "bar", "ipsum", "foo", "baz'

but what I want to return is a list of all possible "Between" strings like:

[
    'baz',
    'baz", "bar", "lorem ipsum',
    'baz", "bar", "lorem ipsum", "bar", "ipsum", "foo", "baz',
    'baz'
]

So given two substrings (Start & end) and a subject string, how can I get all possible substrings between start and end in subject? The most computationally efficient solution is of course desirable.

python-3.x python regex string
4 Answers

Here is a working approach, reasonably efficient I would say.

  • using re.finditer, find indices/spans of the starting and end patterns
  • create all reasonable combinations of the indices/spans
  • slice out the result
subject = '"lorem ipsum", "foo", "baz", "bar", "lorem ipsum", "bar", "ipsum", "foo", "baz", "bar"'

import re
# spans of "start" pattern
sSpans = [match.span() for match in re.finditer('foo", "' ,subject)]
# spans of "end"   pattern
eSpans = [match.span() for match in re.finditer('", "bar"',subject)]
# all possible combination of "between" spans
spans = [(s[1],e[0]) for s in sSpans for e in eSpans] 
# filter only reasonable spand where end > start
spans = [(s,e) for s,e in spans if e > s]
# slice out the "between strings"
result = [subject[s:e] for s,e in spans]
for r in result: print(r)

can also be compressed to one line:

result = [subject[s.span()[1]:e.span()[0]] for s in re.finditer('foo", "' ,subject) for e in re.finditer('", "bar"',subject) if e.span()[0] > s.span()[1]]
for r in result: print(r)
user_27001040

You may use a solution like this one, you just need to modify it a little bit to account for your regex requirements:

import re

def findall_overlapped(r, s):
  res = []                     # Resulting list
  reg = r'^{}$'.format(r)      # Regex must match full string
  for q in range(len(s)):      # Iterate over all chars in a string
    for w in range(q,len(s)):  # Iterate over the rest of the chars to the right
        cur = s[q:w+1]         # Currently tested slice
        m = re.match(reg, cur) # If there is a full slice match
        if m:
            res.append(m.group(1))    # Append Group 1 value to the resulting list
  return res

rx = r'foo", "(.*?)", "bar"'
text = '"lorem ipsum", "foo", "baz", "bar", "lorem ipsum", "bar", "ipsum", "foo", "baz", "bar"'
for s in findall_overlapped(rx, text):
    print(s)

Output of the Python code demo:

baz
baz", "bar", "lorem ipsum
baz", "bar", "lorem ipsum", "bar", "ipsum", "foo", "baz
baz
user_38329700

Here's one way to get the correct answer. It searches for the first term and for each entry, searches the rest of the list for the second term.

subject = ["lorem ipsum", "foo", "baz", "bar", "lorem ipsum", "bar", "ipsum", "foo", "baz", "bar"]

sch1 = "foo"
sch2 = "bar"

all = []

for i1 in  range(len(subject)):  # search first term
   if subject[i1] == sch1: # found first term
       for i2 in range(i1, len(subject)):  # search second term
           if subject[i2] == sch2:   # found second term
               all.extend(subject[i1+1:i2])  # add to main list

print(all)

Output (formatted)

['baz', 
 'baz', 'bar', 'lorem ipsum', 
 'baz', 'bar', 'lorem ipsum', 'bar', 'ipsum', 'foo', 'baz', 
 'baz']
user_138780340

Probably not the fastest solution:

from timeit import default_timer as timer                                                                                                                                                                

subject = '"lorem ipsum", "foo", "baz", "bar", "lorem ipsum", "bar", "ipsum",     "foo", "baz", "bar"'

key1 = 'foo", "'
key2 = '", "bar"'

t_start = timer()

keyl1 = []
keyl2 = []
result = []

start = 0 
start2 = 0
end = len(subject)

while True:
    keyl1.append(subject.find(key1,start,end))
    start = keyl1[-1]+1
    if keyl1[-1] == -1:
       break
   start2 = start
   while True:
       keyl2.append(subject.find(key2,start2,end))
       if keyl2[-1] == -1:
           keyl2 = []
           break
       if keyl2[-1]>keyl1[-1]:
           result.append(subject[keyl1[-1]+len(key1):keyl2[-1]])
       start2 = keyl2[-1]+1

for r in result:
    print(r)

t_end = timer()
print('Seconds: ', t_end - t_start)
user_141624740
Related