Алгоритм поиска общих частей строк

[myst]

Как я понял, у нас на форуме есть действующие программисты.
Ищу сабж. Пока безрезультатно. Где рыть?

[Алексей Гринь]

На примере? Не воткну.

[O]

http://computers.plib.ru/programming/Assembler/Pr/Index7.htm

[GaLL]

Как я понял, у нас на форуме есть действующие программисты.
Ищу сабж. Пока безрезультатно. Где рыть?

В смысле, наибольшую общую подстроку двух строк?

[myst]

http://computers.plib.ru/programming/Assembler/Pr/Index7.htm

Ну зачем же сразу в клуп садо-мазо-то отправлять?

[myst]

Объясняю.
Есть, значит, у нас список строк: предприниматель, законодатель, предстать, верстать, устать.
Нужна функция, выдающая список общих частей, а также информацию, у скольких строк данная общая часть встречается. В нашем случае это будут: пред (2), атель (2), стать (3).
Примерно так.

[злой]

man grep

[Алексей Гринь]

Если массивы данных не большие - всё просто, почарово сравнивать, не вижу проблемы.
Если массивы гигабайтные, то там да, без мудрёного алгоритма не обойтись

[O]

почарово сравнивать

Настоящие лингвисты не работают с однобайтными кодировками!  8)  

[Алексей Гринь]

Настоящие лингвисты не работают с однобайтными кодировками!  8)  

У настоящих лингвистов чар определён в 2-4 байта 8)
В C# например так.

[O]

В C# например так.

Но ведь писателю на С# не нужно искать никаких алгоритмов. Пользуются теми, которые зашиты в библиотеку, а другими — не положено! 

[Алексей Гринь]

Но ведь писателю на С# не нужно искать никаких алгоритмов. Пользуются теми, которые зашиты в библиотеку, а другими — не положено!

С чего это вдруг? Что за бред?

[O]

С чего это вдруг? Что за бред?

Ага, смайликов не замечаем, да? 

[Алексей Гринь]

Ага, смайликов не замечаем, да? 

Не нужно искать алгоритмы, если во фреймворке нет даже класса Set, оный наличествует в большинстве библиотек общего назначения для "хацкерного" СиПоПа?
8)

[Алексей Гринь]

Не очень просто понимаю юмор фразы. Практически у всех языков есть стандартные библиотеки с уже готовыми алгоритмами. СиШарп не исключение.

[myst]

man grep

Подробнее, пжалста. Возможно, я не умею его готовить.

[myst]

Если массивы данных не большие - всё просто, почарово сравнивать, не вижу проблемы.

Это ж не просто сравнение. Да и изобретать самокат тоже лень. Хочется готовенького.

[GaLL]

Объясняю.
Есть, значит, у нас список строк: предприниматель, законодатель, предстать, верстать, устать.
Нужна функция, выдающая список общих частей, а также информацию, у скольких строк данная общая часть встречается. В нашем случае это будут: пред (2), атель (2), стать (3).
Примерно так.

Но ведь здесь есть много других подстрок, например, -пр-.

[myst]

Но ведь здесь есть много других подстрок, например, -пр-.

Я же не робат — всё не углядел.
Длину кусочков я планирую задавать в параметрах.

[GaLL]

Просто постановка задачи неясна. И, как правильно заметил Алексей Гринь, важен объем обрабатываемой информации.

[GaLL]

Длину кусочков я планирую задавать в параметрах.

Если, например, надо посчитать статистику для кусков конкретной длины k, то это можно эффективно сделать при помощи хэширования. Получится линейный относительно суммарной длины всех слов алгоритм.

[myst]

Просто постановка задачи неясна.

Как?! Всё ещё не ясна?!

И, как правильно заметил Алексей Гринь, важен объем обрабатываемой информации.

Размер входного списка около 70 000 слов.

[myst]

Если, например, надо посчитать статистику для кусков конкретной длины k, то это можно эффективно сделать при помощи хэширования. Получится линейный относительно суммарной длины всех слов алгоритм.

Так-так! А подробнее?

[Алексей Гринь]

Размер входного списка около 70 000 слов.

Это для себя нужно?
Если так, могу набросать быдлоалгоритм, который будет работать долго, но сделает своё дело

[myst]

Это для себя нужно?

Да.

Если так, могу набросать быдлоалгоритм, который будет работать долго, но сделает своё дело

Я и сам могу набросать, была бы идея.