# 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]:
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