배열을 비교하여 일치하는 모든 하위 배열을 찾으십시오.

Question

두 개의 숫자 배열 (중복 없음)을 비교하여 원래 배열 모두에 나타나는 길이가 2 이상인 모든 하위 배열을 찾고 싶습니다.

나는 이것을 구현하는 가장 효율적인 방법을 찾고있다.

Answer 1

이것은 나를 상기시켜줍니다 Longest Common Substring Problem 위키 페이지를 읽으십시오. 문제에 대한 좋은 설명, 좋은 참고 자료 및 의사 코드가 있습니다. 해결 방법에는 접미어 트리와 동적 프로그래밍 두 가지가 있습니다. 접미사 트리가보다 효율적인 솔루션 인 것처럼 보이지만 구현에 따라 다소 복잡 할 수 있습니다.

Dynamic Programming에 익숙하지 않은 독자는 여기를 읽어보십시오. 문제와 Longest Common Substring 사이의 유일한 차이점은 문자열에 반복 문자가있는 반면 고유 한 정수 배열이 있다는 것입니다.

이점을 활용할 수도 있지만, 효율성 향상에 큰 도움이되지는 않을 것입니다.