Watto and Mechanism (Codeforces 514C)
Tags: Others, string suffix structures

Watto, the owner of a spare parts store, has recently got an order for the mechanism that can process strings in a certain way. Initially the memory of the mechanism is filled with n strings. Then the mechanism should be able to process queries of the following type: "Given string s, determine if the memory of the mechanism contains string t that consists of the same number of characters as s and differs from s in exactly one position".Watto has already compiled the mechanism, all that's left is to write a program for it and check it on the data consisting of n initial lines and m queries. He decided to entrust this job to you.

Input: The first line contains two non-negative numbers n and m (0 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — the number of the initial strings and the number of queries, respectively.Next follow n non-empty strings that are uploaded to the memory of the mechanism.Next follow m non-empty strings that are the queries to the mechanism.The total length of lines in the input doesn't exceed 6·105. Each line consists only of letters 'a', 'b', 'c'.

Output: For each query print on a single line "YES" (without the quotes), if the memory of the mechanism contains the required string, otherwise print "NO" (without the quotes).


Sample Inputs:
2 3
aaaaa
acacaca
aabaa
ccacacc
caaac

Sample Outputs:
YES
NO
NO

Solution (Python):
(n, m) = map(int, input().split())
M = 99999999999999
v = set()
for i in range(n):
    s = input()
    l = len(s)
    pow = 1
    h = 0
    for i in range(l):
        h = (h + ord(s[i]) * pow) % M
        pow = pow * 203 % M
    pow = 1
    for i in range(l):
        for j in range(97, 100):
            if ord(s[i]) != j:
                v.add((h + (j - ord(s[i])) * pow) % M)
        pow = pow * 203 % M
ans = []
for i in range(m):
    s = input()
    pow = 1
    h = 0
    for i in range(len(s)):
        h = (h + ord(s[i]) * pow) % M
        pow = pow * 203 % M
    ans.append('YES' if h in v else 'NO')
print('\n'.join(ans))

Solution (Python):
from sys import stdin
from functools import reduce
from collections import defaultdict
_data = iter(stdin.read().split('\n'))

def input():
    while True:
        return next(_data)
(n, m) = [int(x) for x in input().split()]
B = 10007
MOD = 1000000000000000003
h = lambda s: reduce(lambda s, c: (B * s + ord(c)) % MOD, s, 0)
hs = defaultdict(set)

def insert(s):
    hs[len(s)].add(h(s))

def find(s):
    v = h(s)
    b = 1
    for c in reversed(s):
        for d in 'abc':
            if c != d:
                u = (v - b * ord(c) + b * ord(d)) % MOD
                if u in hs[len(s)]:
                    return True
        b *= B
        b %= MOD
    return False
for i in range(n):
    s = input()
    insert(s)
out = []
for i in range(m):
    s = input()
    out.append('YES' if find(s) else 'NO')
print('\n'.join(out))

Solution (Python):
from sys import stdin
from functools import reduce
from collections import defaultdict
_data = iter(stdin.read().split('\n'))

def input():
    while True:
        return next(_data)

def insert(s):
    hs[len(s)].add(h(s))

def found(s):
    v = h(s)
    b = 1
    for c in reversed(s):
        for d in 'abc':
            if c != d:
                u = (v - b * ord(c) + b * ord(d)) % MOD
                if u in hs[len(s)]:
                    return True
        b *= B
        b %= MOD
    return False
(n, m) = [int(x) for x in input().split()]
B = 10007
MOD = 1000000000000000003
h = lambda s: reduce(lambda s, c: (B * s + ord(c)) % MOD, s, 0)
hs = defaultdict(set)
for i in range(n):
    s = input()
    insert(s)
text = []
for i in range(m):
    s = input()
    text.append('YES' if found(s) else 'NO')
print('\n'.join(text))