pastebin

Paste Search Dynamic
Recent pastes
defaultdict
  1. from collections import defaultdict
  2. import heapq
  3. def solve(s, ts):
  4.     use = defaultdict(set)
  5.     for i in range(len(s)):
  6.         for j, t in enumerate(ts):
  7.             l = len(t)
  8.             if s[i:i+l] == ts[j]:
  9.                 use[i].add((l, j, i))
  10.  
  11.     q = []
  12.     for l, j, i in use[0]:
  13.         heapq.heappush(q, (-l, j, 0))
  14.  
  15.     #print(use)
  16.     #print(q)
  17.     i = 1
  18.     res = []
  19.     end = 0
  20.     while q:
  21.         l, j, st = heapq.heappop(q)
  22.         res.append((j, st))
  23.         end =-l
  24.         if end >= len(s):
  25.             break
  26.         for ii in range(i, end+1):
  27.             for ll, jj, ss in use[ii]:
  28.                 heapq.heappush(q, (-(ss+ll), jj, ss))
  29.         i = end
  30.         #print(q)
  31.     return res if end >= len(s) else -1
  32.  
  33.  
  34. T = int(input())
  35. for _ in range(T):
  36.     s = input()
  37.     n = int(input())
  38.     ts = []
  39.     for _ in range(n):
  40.         ts.append(input())
  41.     res = solve(s, ts)
  42.     if res == -1:
  43.         print(-1)
  44.     else:
  45.         print(len(res))
  46.         for x, y in res:
  47.             print(str(x+1) + " " + str(y+1))
  48.  
  49.  
Parsed in 0.191 seconds