Codeforces 514C

問題

a,b,cの3文字からなる、n個の文字列が与えられる。
次に、a,b,cの3文字からなる、m個の文字列が一つずつ与えられたとき、n個の文字列で以下の条件を満たす文字列がある場合YES、なければNOを返す。
・同じ長さの文字列である
・ちょうど1つの文字が異なっている

n,m<=3*10^5
the total length of lines in the input<6*10^5

考え方

各文字列の長さが不明だけど、全体で6*10^5程度であるので、そこまで長い文字列が連続することは無い。
が、単純にn個と比較すると、O(n*m*文字列長)であるので無理そう。

n個の文字列をtrieに入れておいて、探索するときに文字を1文字だけ変えたものを全探索することを考える。
trieをたどる際に、「どのノードにいるか？」「これまで何回文字を変更したか？」を状態にたどっていき、与えられた文字列の長さまで探索したときに、そこに文字列が存在するか？を確認すればよい。