[Medium] RequiredSubstrings

평범한 DP를 생각하려고 하면 words[] 끼리 서로 겹치는 부분이 존재할 때, 상태를 어떻게 정의해야할지 막막하다. 패턴이 여러개 뒤섞여 등장하는 경우, Aho-Corasick 알고리즘의 DFA를 이용하면 깔끔하게 상태를 정의할 수 있다. 먼저 words[] 를 갖고 DFA를 만든다. 그리고 여기에 DP를 끼얹는다. meet[u] = DFA상의 노드u에서 매칭되는 패턴의 집합 이건 노드u에서 output link 를 따라가면 쉽게 구할 수 있다. D[i][u][s] = 길이i 이고 현재 DFA상에서 노드 u에 위치한 상태. 지금까지 등장한 패턴의 집합이 s. 일 때, 가능한 문자열의 수 D[i+1][v][s ∪ meet[v]] += D[i][u][s] (DFA상에 u->v 인 간선이 존재할 때) 답은 sum( D[L][u][s] , u는 DFA상의 모든 노드 , s는 정확히 C개를 포함한 모든 집합 )