7575 바이러스

N개의 숫자열 중에서 길이가 K개 이상이면서, 모든 숫자열에 포함되어있는 숫자열이 존재하면 바이러스가 있다고 한다. 단, 이 숫자열을 거꾸로 뒤집었을 때 포함되어 있어도 존재한다고 판단한다. 바이러스가 있으면 YES, 없으면 NO를 출력하는 문제이다.

이 문제는 TLE가 촉박한 문제이다.
원래 같으면 한 줄을 잡아서,  길이 K의 윈도우를 슬라이딩 해가면서 다른 줄과 비교하기만 하면 끝이지만, 이 비교하는 과정에서 최악으로 O(n^2)의 시간복잡도를 가지게 된다. 시간제한은 1초 밖에 안되기 때문에 알고리즘을 따로 만들어줘야 한다.

이 문제는 사실 범위가 1~10000이라 그렇지 문자열 매칭과 똑같은 방법으로 풀 수 있다.
따라서 문자열 매칭에 유명한 알고리즘인 kmp 를 사용하여 비교해주었다. kmp 알고리즘은 시간복잡도가 O(nk)를 보여서, 선형시간에 비교를 마칠 수 있다.

거꾸로 해야 포함되는것은, 슬라이딩 하는 한 줄을 거꾸로 돌려서 다시 비교해도되고, 비교하는 다른 줄을 거꾸로 돌려서 비교해도 된다.

p.s. 한 줄에서 길이를 K만 잡는 이유는 K보다 높은 길이에서 바이러스가 존재하면, K개에서도 바이러스가 존재하기 때문이다.

소스