2016-06-03 5 views
4

backgound에 (간체)3 개 이상의 문자열로 공통 부분을 찾는 방법은 무엇입니까?

I've 프로그래밍 원래 템플릿을 복원하려고 자동으로 생성 된 제 3 자에 의해이 (여러 가지 다른 주소의 출력이 병합 생각)하는 것이 파일과 미안 많이 있어요 및 주소/사용자 정의 데이터.

무엇 I've 두 개의 파일을 diff를하는 라이브러리의 많음 (jsdiff, difflib)이있다 지금까지

바라 보았다. 이 개 파일이 단계에서 지금

질문

그래서 같은 템플릿에서 미안를하면 좋은 지표이다 - I've은 변경된 %의 단어를 알아 내기 위해 그렇게하는 것이 도움이되었다고합니다 함께 유사한 텍스트 파일을 그룹화하는 데에, 이제 더 낫다고 이상적 차이에서 동일한 텍스트를 분리, 그 모든 diff를 할 수있는 방법을 찾을 :

그래서
Hello [Mr, Mrs] [NameA, NameB, NameC...], we are pleased to (...) 

, 어떻게 세 이상의 문자열의 공통 부분을 찾을 수 있습니다 자바 스크립트/파이썬?

+0

https://www.diffchecker.com 또는 다른 "diff" – dandavis

+0

@dandavis이 광고/스팸입니까? 양방향 온라인 diff 도구는 도움이되지 않습니다 ... – thomasf1

+1

@DomTomCat 나는 당신의 (삭제 된) 대답을 읽을 수 있다고 생각합니다. "아니, 그렇지 않아.하지만 당신은 래퍼와 비표준 델타를 사용할 수있다. 그것 difflib 함께. " 토마스, 아마도 당신이 기대할 수있는 가장 좋은 대답 일 겁니다. 때때로 사물이 아직 존재하지 않습니다. – Kittsil

답변

2

접미어 트리가 필요하다고 생각합니다 (wikipedia). 각 문서의 접미어 트리를 작성하십시오. 개별적인 문자를 신경 쓰지 않는다면 문자 대신 자유롭게 단어를 사용할 수 있습니다.

일단 이것을 사용하면 모든 (또는 대부분의) 개별 접미어 트리에서 찾을 수있는 루트에서 가장 긴 경로를 찾아야합니다. 그래서 하나를 선택하고, 모든 노드의 루트를 얻고, DFS를 수행하고, 모든 (또는 충분히 많은) 트리에서 찾을 경우에만 링크를 내려갑니다. 이렇게하면 모든 문서에서 공통적 인 모든 하위 문자열을 반복합니다.

이 모든 것을 이미 수행하는 lib가 있는지는 확실하지 않지만 이미 접미어 트리를 작성하는 데 도움이되는 항목이 있어야합니다.

관련 문제