Find all Occurences of Every Substring in String
python, regex, string
Solution
While jurgenreza has explained why your program didn't work, the solution is still quite slow. If you only examine substrings `s` for which you know that `s[:-1]` repeats, you get a much faster solution (typically a hundred times faster and more):
from collections import defaultdict
def pfind(prefix, sequences):
collector = defaultdict(list)
for sequence in sequences:
collector[sequence[0]].append(sequence)
for item, matching_sequences in collector.items():
if len(matching_sequences) >= 2:
new_prefix = prefix + item
yield (new_prefix, len(matching_sequences))
for r in pfind(new_prefix, [sequence[1:] for sequence in matching_sequences]):
yield r
def find_repeated_substrings(s):
s0 = s + " "
return pfind("", [s0[i:] for i in range(len(s))])
If you want a dict, you call it like this:
result = dict(find_repeated_substrings(s))
On my machine, for a run with 2247 elements, it took 0.02 sec, while the original (corrected) solution took 12.72 sec.
(Note that this is a rather naive implementation; using indexes of instead of substrings should be even faster.)
Edit: The following variant works with other sequence types (not only strings). Also, it doesn't need a sentinel element.
from collections import defaultdict
def pfind(s, length, ends):
collector = defaultdict(list)
if ends[-1] >= len(s):
del ends[-1]
for end in ends:
if end < len(s):
collector[s[end]].append(end)
for key, matching_ends in collector.items():
if len(matching_ends) >= 2:
end = matching_ends[0]
yield (s[end - length: end + 1], len(matching_ends))
for r in pfind(s, length + 1, [end + 1 for end in matching_ends if end < len(s)]):
yield r
def find_repeated_substrings(s):
return pfind(s, 0, list(range(len(s))))
This still has the problem that very long substrings will exceed recursion depth. You might want to catch the exception.
Problem
I am trying to find all occurrences of sub-strings in a main string (of all lengths). My function takes one string and then returns a dictionary of every sub-string (which occurs more than once, of course) and how many times it occurs (format of the dictionary: `{substring: # of occurrences, ...}`). I am using `collections.Counter(s)` to help me with it. Here is my function: ``` from collections import Counter def patternFind(s): patterns = {} for index in range(1, len(s)+1)[::-1]: d = nChunks(s, step=index) parts = dict(Counter(d)) patterns.update({elem: parts[elem] for elem in parts.keys() if parts[elem] > 1}) return patterns def nChunks(iterable, start=0, step=1): return [iterable[i:i+step] for i in range(start, len(iterable), step)] ``` I have a string, `data` with about 2500 random letters (in a random order). However, there are 2 strings inserted into it (random points). Say this string is 'TEST'. `data.count('TEST')` returns 2. However, `patternFind(data)['TEST']` gives me a `KeyError`. Therefore, my program does not detect the two strings in it. What have I done wrong? Thanks! Edit: My method of creating testing-instances: ``` def createNewTest(): n = randint(500, 2500) x, y = randint(500, n), randint(500, n) s = '' for i in range(n): s += choice(uppercase) if i == x or i == y: s += "TEST" return s ```