최대 동일한 문자열

이의 내가 두 문자열을 있다고 가정 해 봅시다 서브 어레이.최대 동일한 문자열

기본적으로

"ABBABBA" 
"BBABCBA" 
Maximum subarray: "BBAB" 
Size: 4

, 어떻게 가장 효율적인 방법으로이 문제를 해결할 수 있습니다 : 여기

은 또 다른 예입니다?

이 다른 문자열에 대한 모든 하위 어레이를 생성 한 캐릭터의 모든 하위 어레이를 생성;

내 생각은 다음이다
는
결과는 최대 규모의 매칭 서브 어레이

의 크기입니다하지만이 나쁜 보이는 무력하다고 생각하는 모든 하위 어레이를 비교. 이걸 어떻게 개선 할 수 있을지 생각해?

감사합니다.

편집 문자열도 필요합니다.

출처

2012-04-19 David Gomes

가장 긴 공통 부분 시퀀스 문제입니까? 어쩌면이 http://rosettacode.org/wiki/Longest_common_subsequence는 C++이 없더라도 도움이 될 것입니다! – ShinTakezou

@ShinTakezou 아니요, 가장 긴 공통 부분 문자열입니다 * - LCS보다 훨씬 쉽습니다. – dasblinkenlight

@ dasblinkenlight 감사합니다. 너무 빨리 읽고 생각하지 못했습니다. – ShinTakezou

이 내용은 Longest Common Substring이라는 잘 알려진 문제입니다. O(mn)에서 해결할 수 있습니다. m 및 n은 동적 프로그래밍 접근 방식을 사용하여 개별 문자열의 길이입니다. Wikipedia의 기사에는 따라하기 쉬운 의사 코드가 들어 있습니다.

출처

2012-04-19 16:54:49 dasblinkenlight

하지만 알고리즘을 통해 길이가 반환됩니다. 문자열도 필요합니다. –

@ user996056 기사에 다양한 언어로 구현되는 [link] (http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring)이 있습니다. 두 번째 C# 구현은 문자열을 반환합니다. – dasblinkenlight

O (mn)보다 훨씬 더 잘 풀 수 있습니다. 최적 해는 O (m + n)이며, 이는 여러 가지 그래프 알고리즘을 통해 얻을 수 있습니다. – ex0du5

최대 동일한 문자열

답변

관련 문제