[AC] 1701 Cubeditor

출처 : https://www.acmicpc.net/problem/1701

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1707.cpp

정답 소스에 1707이라는 실수를 하였다. 그냥 넘어가야지..

암튼 이문제는 서픽스어레이를 활용한 문제이다. 물론 KMP를 써도 풀릴것 같은데 내가 해보니 참 어려웠다.

그리고 suffix array를 쓰는게 훨~ 씬 간단하게 풀린다.

하지만 아직 suffix array 구현 방법을 모르겠다 ㅠㅠ 공부중이다. 나중에 공부가 끝나면 다시 풀어봐야겠다.

내가 푼 방법은 테스트케이스가 적기 때문에 가능한 풀이법이다.

결론은 LCP를 활용하였지만, suffix array가 생명인 것이다.

그런데 찾고보니 최적의 알고리즘은 O(n)으로도 할 수 있다는데 도대체 어떤 방식인지 궁금하였다. 

암튼 이 문제도 1년이 넘는 시간만에 드디어 풀었다.