동적 프로그래밍이나 접미사 트리가없는 가장 긴 공통 부분 문자열

Question

Skiena의 알고리즘 디자인 매뉴얼 질문 8-3 파트 b는 동적 프로그래밍에 의존하지 않는 가장 긴 공통 부분 문자열을 찾기위한 "간단한"BigO (nm) 알고리즘을 제공합니다. 명백한 대답은 접미사 트리를 사용하는 것 같습니다. 그러나 Skiena는 "Simpler"라는 단어를 사용합니다. 접미어 트리가 DP보다 간단하고 어쩌면 검색이 더 쉬울 지 모르지만 nm 시간 복잡도에서 접미어 트리를 만드는 것은 아무 것도 아니라 단순한. 그래서, O (nm) 시간에서이 문제를 해결할 다른 방법이 있습니까?

Answer 1

시작 위치 i을 첫 번째 (더 짧은) 문자열 s에 고정 시켰다고 가정 해 보겠습니다. 이제 긴 문자열에서 가능한 가장 긴 접두사를 찾으십시오. 문자열 s[i:] + # + t의 prefix function (또는 z function)을 검사하여 O(n + m)에서 수행 할 수 있습니다. 여기서 #은 s 및 t 중 하나에 존재하지 않는 특수 기호입니다.

전반적 복잡성 O(nm) 경우 N <미터

이다 O(n(n + m))이고