BOJ 9250 문자열 집합 판별

Aho-Corasick 알고리즘의 기본 문제입니다. Needle의 집합의 문자열들의 길이의 합이 $N$이고 haystack의 길이가 $M$이며 그 안에 needle의 등장 횟수의 합이 $K$이면, Aho-Corasick 알고리즘은 $\mathcal{O} (N+M+K)$에 모든 needle의 모든 등장 위치를 찾을 수 있습니다.

최악의 입력에서 $K$는 $\mathcal{O} (NM)$일 수 있지만, 이 문제에서는 하나의 needle이 발견되면 즉시 종료할 수 있으므로 $K$를 뗄 수 있습니다.