Как сравнить набор строк, чтобы найти общие подстроки

Я пытаюсь создать скрипт, который просматривает список строковых файлов и сообщает о наиболее распространенных между ними подстроках.

Например:

  1. Здравствуйте, я первая строка. Я люблю яблоки и апельсины. Мы все здесь струны.
  2. Здравствуйте, я вторая строка. Я люблю яблоки и апельсины. Мы все здесь струны.
  3. Здравствуйте, я третья строка. Я люблю яблоки и апельсины. Мы все здесь струны.
  4. Привет, я строка четыре. Я люблю яблоки и апельсины. Мне нравится выражать свою индивидуальность.

Я хочу, чтобы скрипт сообщал мне, какие общие элементы между строками выше определенного порога (например, 5 символов).

В идеале мне сказали бы

  • «Я люблю яблоки и апельсины» встречается во всех файлах.
  • «Привет, я строка» встречается во всех файлах
  • «Мы все здесь строки» встречается в трех файлах.

Если существуют функции для этого в технологиях, с которыми я знаком - SQL, Javascript, PHP, Ruby или Bash - я буду очень рад...

Большое спасибо,

разъем


person Jack Shepherd    schedule 13.01.2011    source источник
comment
Этот вопрос тесно связан и имеет много соответствующих ответов: stackoverflow.com/questions/1410822/   -  person Anderson Green    schedule 04.06.2013


Ответы (1)


Это сложная проблема, известная как самая длинная общая проблема с подпоследовательностью.

Вот реализация алгоритма на Python с использованием динамического программирования: .php/Longest_Common_Subsequence

Я не думаю, что какая-либо стандартная библиотека (C, Java, PHP, Python, Javascript, Ruby и т. д.) имеет такую ​​функцию. Но вы можете поискать реализации здесь: http://www.google.com/codesearch?q=%22longest+common+subsequence%22

person scoffey    schedule 13.01.2011
comment
А, спасибо за это. Теперь я знаю имя, которое мне удалось найти в некоторых готовых реализациях: en.wikibooks .org/wiki/Algorithm_implementation/Strings/ - person Jack Shepherd; 13.01.2011