Thursday, August 27, 2015

Latin America Regional Contests 2010 G번(BOJ 5699번)

문제 링크(acmicpc.net 5699번)

Aho-Corasick 알고리즘으로 풀 수 있다.

주어지는 입력 문자열들로 트라이를 구성하고, 기존의 노드(x)에서 새로 뻗어나가는 노드(y)의 실패링크(yf) 걸어줄 때

d[y] = max(d[x], d[yf]) + "노드 y에서 끝나는 string의 개수"

O( 문자열의 길이의 합 ) 에 해결할 수 있다.

내 소스 코드

No comments:

Post a Comment