Cod sursa(job #2532917)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 28 ianuarie 2020 16:35:42
Problema Potrivirea sirurilor Scor 40
Compilator py Status done
Runda Arhiva educationala Marime 1.01 kb
def solve(n, m, a, b):
    ans = []
    """ a appears in b
        pos[i] = how many characters match the suffix of a[:i + 1] with the prefix of a[1:]
    """
    pos = [0 for _ in range(n + 1)]
    pos[1] = 0
    k = 0
    for i in range(2, n + 1):
        while k != 0 and a[k + 1] != a[i]:
            k = pos[k]
        if a[k + 1] == a[i]:
            k += 1
        pos[i] = k

    k = 0
    for i in range(1, m + 1):
        while k != 0 and a[k + 1] != b[i]:
            k = pos[k]
        
        if a[k + 1] == b[i]:
            k += 1
        if k == n:
            ans.append(i - n + 1 - 1)
            k = pos[k]

    return ans

if __name__ == "__main__":
    with open('strmatch.in', 'rt') as fin:
        a = 'a' + next(fin).strip()
        b = 'a' + next(fin).strip()
        n, m = len(a) - 1, len(b) - 1
    ans = solve(n, m, a, b)
    with open("strmatch.out", 'wt') as fout:
        fout.write('{}\n'.format(len(ans)))
        for v in ans[:1000]:
            fout.write('{} '.format(v))
        fout.write('\n')