• + 0 comments

    python

    def rid(s):
        n, a, b, r = len(s), 0, 0, [0] * len(s)
        for i in range(1, n):
            if r[i - a] < b - i + 1:
                r[i] = r[i - a]
            else:
                a, b = i, max(i, b)
                while b < n and s[b - a] == s[b]:
                    b += 1
                r[i], b = b - a, b - 1
        return r
    
    def virusIndices(P, V):
        p, v, res, r1, r2 = len(P), len(V), [], rid(V + " " + P), rid(V[::-1] + " " + P[::-1])
        for i in range(p - v + 1):
            if r1[v + 1 + i] == v or r1[v + i + 1] + r2[p + 1 - i] + 1 >= v:
                res.append(i)
        print(" ".join(str(x) for x in res) if len(res) else "No Match!")