가장 쉬운 문자열 자료구조나 알고리즘은 무엇일까? 아마 트라이정도가 있을 것이다. 이런 트라이도 상당히 고난이도의 자료구조에 속하기 때문에 문자열을 사용하는 자료구조나 알고리즘은 많이 어렵다. 문자열의 꽃이라고 볼 수 있는 Suffix 자료구조도 굉장히 고난이도에 속한다. 우리나라에서는 Suffix Array나 Suffix Tree (Suffix Trie) 등이 알려져있지만 Suffix Automaton은 잘 알려져있지 않다. 여기에서는 엄밀한 증명은 제외하고 Suffix Automaton이 무엇인지 알아보도록 한다. Automaton이름에서 볼 수 있듯이 Suffix Automaton은 어떤 문자열의 Suffix로 Automaton을 그린 것이다. Automaton가 뭔지 모른다면 여기를 참고하자. S..
