티스토리 뷰

ICPC/2014 인터넷예선

G. Mutation

전명우 2014. 10. 8. 00:34

길이가 N인 문자열이 주어지고, 길이가 M인 패턴이 주어진다. 이 패턴의 연속된 일부분 혹은 전체를 한 번 뒤집어서 새로운 패턴들을 만들 수 있다. 길이가 N인 문자열에서 이렇게 만들어진 패턴들과 매치되는 부분 문자열이 몇 개인지 세어주는 문제다.


N ≤ 1,000,000 이고 M ≤ 100 이다. 시간제한은 0.2초로 N에 선형인 시간복잡도를 요구한다. 길이가 M인 패턴에서 뒤집는 연산에 의해 만들어지는 새로운 패턴의 개수는 많아야 $M^2$개다.


즉, 이 문제는 길이가 M인 패턴 $M^2$개와 길이가 N인 문자열을 매칭하는 문제로 바꿀 수 있다. 이와 관련된 문제는 Aho-Corasick 자료구조를 이용하면된다. KMP와 같은 문자열 매칭 알고리즘은 하나의 패턴과 전체 문자열을 매칭하는 알고리즘인데, Aho-Corasick은 여러 개의 패턴과 문자열 사이의 매칭을 선형 시간안에 가능하게 해준다.


일반적으로 Aho-Corasick을 구현할 때 까다로운 점은 문자열 사이의 포함 관계인데, 이 문제에서 모든 패턴은 서로 다르고 길이가 같기 때문에 포함 관계가 생기질 않는다. 이로 인해 Aho-Corasick에서 failure link만 잘 계산해주면 해결할 수 있다.


이 문제에서 Aho-Corasick을 구현하는 시간복잡도는 O(M^3)이고, 전체 문자열에 매칭이 되는지 확인해주는 시간복잡도는 O(N)이다. 따라서, 전체 시간복잡도는 O(N + M^3)으로 0.2초 안에 충분히 수행된다.


Aho-Corasick에 대한 자세한 설명은 생략하겠다. 연습 문제로는 문자열 집합 판별 문제가 있다.


'ICPC > 2014 인터넷예선' 카테고리의 다른 글

J. Switch Array  (0) 2014.10.08
K. Traffic Jams  (0) 2014.10.08
G. Mutation  (0) 2014.10.08
E. Highway  (0) 2014.10.07
D. 헨리  (0) 2014.10.07
C. 그리드 그래프  (2) 2014.10.07
댓글
댓글쓰기 폼