문자열 집합에서 최적의 문자열 (최소 길이)을 찾아서 결과 문자열에 모든 문자열이 포함되어야합니다.

Question

두 개의 문자열이 있다고 가정합니다. "abcde"및 "dfbag" 결과 문자열은 "ceabdfg"일 수 있습니다. 결과 문자열 "ceadb"의 처음 다섯 문자는 "abcde"의 anargram입니다. 마지막 5 자 "abdfg"는 두 번째 문자열 (dfbag)의 아나 로그이기도합니다.

두 문자열의 최적 문자열을 쉽게 찾을 수 있습니다.

1. 두 문자열에있는 모든 공통 문자 집합을 가져옵니다. 위의 예제에서 'a', 'd'및 'b'는 두 문자열 모두에 있습니다. (adb, dba, bda 등)

2. 첫 번째 문자열의 나머지 문자를 가져 와서 앞에 둡니다. 'c'와 'e'는 첫 번째 문자열의 남은 문자입니다. 그래서 그들을 앞에 놓으십시오. 그래서 우리는 "ceabd"를 발견했습니다. 그 첫 번째 문자열의 anargram.

3. 두 번째 문자열의 나머지 문자를 가져 와서 문자열 끝에 넣습니다. 'f'와 'g'는 두 번째 문자열에서 남은 문자입니다. 2에서 찾은 문자열 다음에 넣으면 "ceadbfg"가됩니다. 여기서 "adbfg"는 두 번째 문자열의 아나 그램입니다.

제 질문은 N 개의 문자열이있는 경우 최적의 결과 문자열을 찾는 알고리즘이 될 수 있습니까?

예 :.

우리는 "D"

최적의 문자열이 될 수

"DBCA를"4 문자열 "ABC", "카", "BD"를 갖는다. "DBCA"의

부분 문자열 "BCA는", "ABC", "DBCA"의

부분 문자열 "CA"의 anargram하다 "DBCA"의 "캘리포니아"

부분 문자열 "DB"의 anargram은 "DBCA"의 "BD"

하위 문자열 "D"의 anargram 내가이위한 알고리즘을 찾고 있어요 "D"

의 anargram은입니다. (Ofcourse는 모든 조합을 검사하는 무차별 대항력이 아닙니다. :)). 무차별 한 힘없이, 어떤 생각?

Answer 1

이 문제는 NP 완전하고, HAMPATH (그래프에서 해밀턴 경로 찾기)를 줄임으로써이를 보여줍니다.

참고 : 알파벳이 임의로 크다고 생각합니다.

꼭지점 V가 에지 E_V1, E_V2, ..., E_Vk에 입사하는 N 개의 꼭지점 및 M 개의 에지를 갖는 그래프를 고려 해보자. 우리는 각 가장자리에 대해 고유 한 문자를 만듭니다. 이제 각 꼭지점은 문자열 E_V1 E_V2 ... E_Vk (인시던트 가장자리의 모든 문자로 구성된 문자열)에 해당합니다.

길이가 2M 인 N 개의 문자열이 있습니다. 두 개의 꼭지점이 두 개 이상의 가장자리를 공유하지 않으므로 각 두 개의 문자열에는 공통적으로 두 개 이상의 문자가 포함되지 않습니다. 그래서 초정수의 길이는 적어도 2M - (N - 1)입니다 : 두 개의 연속 된 문자열이 문자를 공유하면 발생합니다. 이제 두 개의 후속 정점 사이에 모서리가있는 경우에만이 작업이 수행 될 수 있습니다. 즉 그래프에 해밀턴 경로가 있습니다.

따라서 우리는 다항식 시간에 2M - (N - 1) 길이의 초 수법이 있는지 확인하면 다항식 시간에 HAMPATH를 풀 수 있습니다. 그래서 문제는 NP 하드입니다.

NP 완성도는 명백합니다. 문자열 자체는 인증서입니다.