Match Substring After Replacement

#KMP
#O(max(n, ∆))
#where n = len(s)
#∆ = no. of equivalent new char pairs, who have same old chars
#like if mappings = [['a', '1'], ['a', 'x'], ['b', 'x'], ['b', '3']] (old -> new)
#then, ∆ = 2 (['1', 'x'] and ['3', 'x'])

class Solution:
    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
        n = len(s)
        m = len(sub)

        mp = {}
        for x, y in mappings:
            mp.setdefault(y, set()).add(x)
        mp1 = set()
        for val in mp.values():
            for i in val:
                for j in val:
                    mp1.add((i, j))

        mp2 = set()
        for x, y in mappings:
            mp2.add((x,y))

        eqCheck1 = lambda a, b: (a == b) or ((a, b) in mp1)
        eqCheck2 = lambda a, b: (a == b) or ((a, b) in mp2)

        pre = [0]*(m+1)
        for i in range(1, m):
            x = pre[i - 1]
            while x > 0 and not eqCheck1(sub[x], sub[i]):
                x = pre[x-1]

            if eqCheck1(sub[x], sub[i]):
                pre[i] = x + 1

        x = 0 #already matched
        for i in range(n):
            while x > 0 and not eqCheck2(sub[x], s[i]):
                x = pre[x-1]

            if eqCheck2(sub[x], s[i]):
                x += 1

            if x == m:
                return True

        return False