BOJ 11478 - 서로 다른 부분 문자열의 개수

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다.

방법 1) Suffix Array + LCP
$O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다.

방법 2) 트라이
$O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다.

방법 3) 해싱
$O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다.

코드 (트라이) : http://ideone.com/bugbDy
코드 (해싱) : http://ideone.com/hkjw5n