Masha-forgetful (Codeforces 1624E)
Tags: Others, hashing

Masha meets a new friend and learns his phone number — $$$s$$$. She wants to remember it as soon as possible. The phone number — is a string of length $$$m$$$ that consists of digits from $$$0$$$ to $$$9$$$. The phone number may start with 0.Masha already knows $$$n$$$ phone numbers (all numbers have the same length $$$m$$$). It will be easier for her to remember a new number if the $$$s$$$ is represented as segments of numbers she already knows. Each such segment must be of length at least $$$2$$$, otherwise there will be too many segments and Masha will get confused.For example, Masha needs to remember the number: $$$s = $$$ '12345678' and she already knows $$$n = 4$$$ numbers: '12340219', '20215601', '56782022', '12300678'. You can represent $$$s$$$ as a $$$3$$$ segment: '1234' of number one, '56' of number two, and '78' of number three. There are other ways to represent $$$s$$$.Masha asks you for help, she asks you to break the string $$$s$$$ into segments of length $$$2$$$ or more of the numbers she already knows. If there are several possible answers, print any of them.

Input: The first line of input data contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) —the number of test cases.Before each test case there is a blank line. Then there is a line containing integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^3$$$) —the number of phone numbers that Masha knows and the number of digits in each phone number. Then follow $$$n$$$ line, $$$i$$$-th of which describes the $$$i$$$-th number that Masha knows. The next line contains the phone number of her new friend $$$s$$$.Among the given $$$n+1$$$ phones, there may be duplicates (identical phones).It is guaranteed that the sum of $$$n \cdot m$$$ ($$$n$$$ multiplied by $$$m$$$) values over all input test cases does not exceed $$$10^6$$$.

Output: You need to print the answers to $$$t$$$ test cases. The first line of the answer should contain one number $$$k$$$, corresponding to the number of segments into which you split the phone number $$$s$$$. Print -1 if you cannot get such a split.If the answer is yes, then follow $$$k$$$ lines containing triples of numbers $$$l, r, i$$$. Such triplets mean that the next $$$r-l+1$$$ digits of number $$$s$$$ are equal to a segment (substring) with boundaries $$$[l, r]$$$ of the phone under number $$$i$$$. Both the phones and the digits in them are numbered from $$$1$$$. Note that $$$r-l+1 \ge 2$$$ for all $$$k$$$ lines.

Note: The example from the statement.In the second case, it is impossible to represent by segments of known numbers of length 2 or more.In the third case, you can get the segments '12' and '21' from the first phone number.

Sample Inputs:
5
4 8
12340219
20215601
56782022
12300678
12345678
2 3
134
126
123
1 4
1210
1221
4 3
251
064
859
957
054
4 7
7968636
9486033
4614224
5454197
9482268

Sample Outputs:
3
1 4 1
5 6 2
3 4 3
-1
2
1 2 1
2 3 1
-1
3
1 3 2
5 6 3
3 4 1

Solution (Python):
import sys
input = lambda : sys.stdin.readline()[:-1]

def split_across_impossible(number, twos):
    output = []
    last_split = 0
    for i in range(len(number) - 1):
        code = int(number[i:i + 2])
        if twos[code] is None:
            output += [number[last_split:i + 1]]
            last_split = i + 1
    output += [number[last_split:]]
    return output

def estimate_segments(fragment, _twos, _threes):
    len_f = len(fragment)
    if len_f % 2 == 0:
        output = []
        for i in range(len_f // 2):
            output += [_twos[int(fragment[2 * i:2 * i + 2])]]
        return output
    for j in range((len_f - 3) // 2 + 1):
        code = int(fragment[2 * j:2 * j + 3])
        if _threes[code] is None:
            continue
        output = []
        for i in range(j):
            output += [_twos[int(fragment[2 * i:2 * i + 2])]]
        output += [_threes[code]]
        for i in range((len_f - (2 * j + 3)) // 2):
            code = int(fragment[2 * j + 3 + 2 * i:2 * j + 3 + 2 * i + 2])
            output += [_twos[code]]
        return output

def masha_forgetful(n, m, knowns, new):
    _twos = [None] * 100
    _threes = [None] * 1000
    for (idx, known) in enumerate(knowns, 1):
        for i in range(m - 1):
            code = int(known[i:i + 2])
            if _twos[code] is None:
                _twos[code] = (i + 1, i + 2, idx)
        for i in range(m - 2):
            code = int(known[i:i + 3])
            if _threes[code] is None:
                _threes[code] = (i + 1, i + 3, idx)
    fragments = split_across_impossible(new, _twos)
    if any(map(lambda x: len(x) < 2, fragments)):
        sys.stdout.write('-1\n')
        return
    results = []
    for fragment in fragments:
        segments = estimate_segments(fragment, _twos, _threes)
        if segments is None:
            sys.stdout.write('-1\n')
            return
        results += segments
    sys.stdout.write(f'{len(results)}\n')
    for (l, r, idx) in results:
        sys.stdout.write(f'{l} {r} {idx}\n')
for _ in range(int(input())):
    input()
    (n, m) = map(int, input().split())
    knowns = [None] * n
    for i in range(n):
        knowns[i] = input()
    new = input()
    masha_forgetful(n, m, knowns, new)

Solution (Python):
import sys

def split_across_impossible(number, twos):
    output = []
    last_split = 0
    for i in range(len(number) - 1):
        code = int(number[i:i + 2])
        if twos[code] is None:
            output += [number[last_split:i + 1]]
            last_split = i + 1
    output += [number[last_split:]]
    return output

def estimate_segments(fragment, _twos, _threes):
    len_f = len(fragment)
    if len_f % 2 == 0:
        output = []
        for i in range(len_f // 2):
            output += [_twos[int(fragment[2 * i:2 * i + 2])]]
        return output
    for j in range((len_f - 3) // 2 + 1):
        code = int(fragment[2 * j:2 * j + 3])
        if _threes[code] is None:
            continue
        output = []
        for i in range(j):
            output += [_twos[int(fragment[2 * i:2 * i + 2])]]
        output += [_threes[code]]
        for i in range((len_f - (2 * j + 3)) // 2):
            code = int(fragment[2 * j + 3 + 2 * i:2 * j + 3 + 2 * i + 2])
            output += [_twos[code]]
        return output

def masha_forgetful(n, m, knowns, new):
    _twos = [None] * 100
    _threes = [None] * 1000
    for (idx, known) in enumerate(knowns, 1):
        for i in range(m - 1):
            code = int(known[i:i + 2])
            if _twos[code] is None:
                _twos[code] = (i + 1, i + 2, idx)
        for i in range(m - 2):
            code = int(known[i:i + 3])
            if _threes[code] is None:
                _threes[code] = (i + 1, i + 3, idx)
    fragments = split_across_impossible(new, _twos)
    if any(map(lambda x: len(x) < 2, fragments)):
        sys.stdout.write('-1\n')
        return
    results = []
    for fragment in fragments:
        segments = estimate_segments(fragment, _twos, _threes)
        if segments is None:
            sys.stdout.write('-1\n')
            return
        results += segments
    sys.stdout.write(f'{len(results)}\n')
    for (l, r, idx) in results:
        sys.stdout.write(f'{l} {r} {idx}\n')
for _ in range(int(input())):
    input()
    (n, m) = map(int, input().split())
    knowns = [None] * n
    for i in range(n):
        knowns[i] = input()
    new = input()
    masha_forgetful(n, m, knowns, new)

Solution (Python):
def main():
    for _ in range(int(input())):
        dict = {}
        input()
        (n, m) = map(int, input().split())
        lis = []
        for i in range(n):
            lis.append(input())
        actual = input().strip()
        for i in range(n):
            for j in range(m - 1):
                dict[lis[i][j:j + 2]] = [j + 1, j + 2, i + 1]
            for j in range(m - 2):
                dict[lis[i][j:j + 3]] = [j + 1, j + 3, i + 1]
        dp = [False] * (m + 1)
        way = [0] * (m + 1)
        dp[0] = True
        for i in range(2, m + 1):
            if dp[i - 2] == True and actual[i - 2:i] in dict:
                way[i] = dict[actual[i - 2:i]]
                dp[i] = True
            elif dp[i - 3] == True and actual[i - 3:i] in dict:
                way[i] = dict[actual[i - 3:i]]
                dp[i] = True
        if dp[-1] == True:
            ans = []
            ind = m
            while ind >= 2:
                ans += [way[ind]]
                ind -= way[ind][1] - way[ind][0] + 1
            print(len(ans))
            for a in ans[::-1]:
                print(f'{a[0]} {a[1]} {a[2]}')
        else:
            print(-1)
main()