문자열 집합을 비교하여 일반적인 하위 문자열을 찾는 방법

Question

문자열 파일 목록을보고 가장 공통적 인 하위 문자열에 대한 보고서를 만드는 스크립트를 만들려고합니다. 예를 들어

:

1. 안녕하세요, 저는 문자열 하나입니다. 나는 사과와 오렌지를 좋아한다. 우리는 모두 여기에 문자열입니다.
2. 안녕하세요, 저는 두 번째 문자열입니다. 나는 사과와 오렌지를 좋아한다. 우리는 모두 여기에 문자열입니다.
3. 안녕하세요, 저는 문자열 3입니다. 나는 사과와 오렌지를 좋아한다. 우리는 모두 여기에 문자열입니다.
4. 안녕하세요, 저는 4 번 문자열입니다. 나는 사과와 오렌지를 좋아한다. 나는 나의 개성을 표현하고 싶습니다.

스크립트가 특정 임계 값 (예 : 5 자) 이상인 문자열 사이의 공통 요소를 알려주고 싶습니다.

이 이상적으로는

는 "안녕하세요, 저는 문자열입니다"모든 파일에서 발생

• "나는 사과와 오렌지를 좋아한다"
  말했다 거라고하는 것은
• "우리는 모든 문자열이 여기에있는 모든 파일에서 발생 "세 파일에서 발생합니다.

기능을 내가 잘 알고있어 기술에서이 작업을 수행 할 수있는 경우 - SQL, 자바 스크립트, PHP, 루비 또는 배쉬 매우 행복 오티스 ...

많은 감사,

Jack

Answer 1

이것은 어려운 문제로 Longest common subsequence problem입니다. 여기

는 동적 프로그래밍을 사용하여 알고리즘의 파이썬 구현 : http://www.algorithmist.com/index.php/Longest_Common_Subsequence

내가 어떤 표준 라이브러리 (C, 자바, PHP, 파이썬, 자바 스크립트, 루비 등) 등으로 온다 생각하지 않는다

기능. 하지만 여기서 구현을 찾을 수 있습니다 : http://www.google.com/codesearch?q=%22longest+common+subsequence%22