Ich hätte nicht gedacht, dass man die rekursive Variante so schnell bekommt. Also dachte ich, dass man einen anderen Ansatz braucht. def find_pos(pat, txt): return [(i, i+len(pat)) for i in range(len(txt)) if txt.startswith(pat, i)] total = 0 for seq in seqs: # Finde alle Pattern-Positionen pairs = sum([find_pos(pat, seq) for pat in patterns], []) # Baue Verbindungsgraph graph = {} for s, e in pairs: if s not in graph: graph[s] = [] graph[s].append(e) # Berechne Wege (DP) dp = [0] * (len(seq) + 1) dp[0] = 1 for pos in range(len(seq)): if pos in graph: for next_pos in graph[pos]: dp[next_pos] += dp[pos] total += dp[-1]
Ich hätte nicht gedacht, dass man die rekursive Variante so schnell bekommt. Also dachte ich, dass man einen anderen Ansatz braucht.
def find_pos(pat, txt):
return [(i, i+len(pat)) for i in range(len(txt))
if txt.startswith(pat, i)]
total = 0
for seq in seqs:
# Finde alle Pattern-Positionen
pairs = sum([find_pos(pat, seq) for pat in patterns], [])
# Baue Verbindungsgraph
graph = {}
for s, e in pairs:
if s not in graph: graph[s] = []
graph[s].append(e)
# Berechne Wege (DP)
dp = [0] * (len(seq) + 1)
dp[0] = 1
for pos in range(len(seq)):
if pos in graph:
for next_pos in graph[pos]:
dp[next_pos] += dp[pos]
total += dp[-1]