Помогите с этим рваным массивом / подстрокой программы на C?

Question

Итак, у меня есть рваный массив (называемый именами) длиной 200. Каждый указатель в массиве указывает на строку длиной не более 50 символов и без пробелов. У меня также есть строка, заданная через пользовательский ввод, называемая inname, длиной 50, inname будет одной из строк, хранящихся в именах. Мне нужно найти способ просмотреть строки в моем рваном массиве и найти строку с наибольшим перекрытием подстроки с именем inname, исключая само имя, поскольку это будет в файле. Если ни одна строка не перекрывается, то мы выводим «нет рекомендаций». Я таял, пытаясь разобраться в этом уже много часов, помогает? O :) Так что, в основном, программа находит имя в массиве с наибольшим перекрытием подстроки с inname. будет редактировать, чтобы предоставить дополнительную информацию, если вам это нужно

Answer 1

Вероятно, вам следует начать с небольшой проблемы определения размера перекрытия между infunc и одной строкой.

В Википедии рассматриваются некоторые алгоритмы для решения самой длинной общей проблемы подстрок (включая псевдокод!)

Answer 2

Это не приведет вас к самому эффективному способу перекрытия (динамическое программирование - это один из способов - есть и другие сумасшедшие методы, такие как суффиксные деревья), но вам следует начать:

Сначала подумайте, как бы вы нашли длину перекрытия с выравниванием начала обеих строк. Например, найдите самое длинное перекрытие между этими двумя:

programming
ungrammatical

В этом случае перекрывается только одно m - длина 1.

Тогда подумайте, как бы вы "сместили" строки и искали перекрытие, когда они выровнены по-разному. (На самом деле не изменяйте строки: просто измените способ их обхода, чтобы сравнить их.) Какое совпадение между этими двумя?

programming
 ungrammatical

Подумайте, как посмотреть на все возможные выравнивания. Если вы отслеживаете самый длинный из найденных, у вас самое длинное выравнивание между двумя конкретными строками.

После этого перейдите к проверке всех различных строк. Следите за тем, у кого лучший матч, и снова, как только вы посмотрите на все из них, у вас есть ответ.