Trie를 사용하여 가장 긴 공통 부분 문자열 찾기

Question

trie를 사용하여 두 개 이상의 문자열 중에서 LCS (longest common substring)를 어떻게 찾을 수 있습니까?

저는이 아이디어가 있습니다 - 첫 번째 문자열이 "abbcabdd"라고 가정합니다. 그러면 나는 먼저 "abbcabdd"를 trie에 넣고 "bbcabdd", "bcabdd"...., "d"를 그리고 모든 문자열에 대해이 과정을 반복합니다.

그런 다음 트라이를 통과하여 가장 긴 부분 문자열을 계산하십시오.

하지만 효율적이지 않다고 생각합니다. 다른 개선 된 방법이 있습니까?

Answer 1

설명하는 내용은 정확히 suffix tree입니다. 접미사 트리를 생성하는 데 최적화 된 알고리즘을 사용하면 효율성이 향상됩니다!

O(n)에 접미어 트리를 작성하는 알고리즘이 있습니다 (물론 상수 알파벳으로 가정).