Сходство строк в c

Я не уверен, что это лучший алгоритм, но вот решение.

Прежде всего, создайте массив суффиксов. Наивный алгоритм (помещение всех суффиксов в массив, а затем его сортировка) довольно медленный - операции O (n ^ 2 * log (n)), существует несколько алгоритмов для выполнения этого за время O (nlogn).

Я предполагаю, что строки имеют индекс 0.

1. Теперь возьмите первую букву l в строке s и используйте один двоичный поиск, чтобы найти индекс i первой строки в массиве суффиксов, который начинается с l, и другой двоичный поиск, чтобы найти индекс j первой строки в диапазоне. [i..n], который не начинается с l. Тогда вы получите, что все строки в диапазоне [i..j-1] начинаются с одной и той же буквы l. Так что ответ на задачу как минимум j-i.

2. Затем примените аналогичную процедуру к строкам в диапазоне [i..j). Возьмите вторую букву l2, найдите индексы i2 и j2, соответствующие первой строке s[i2] такой, что s[i2][1] == l2, и первой строке s[j2] такой, что s[j2][1] != l2. Добавьте j2-i2 к ответу.

3. Повторите эту процедуру n раз, пока не закончатся буквы в исходной строке. Ответ на задачу j1-i1+j2-i2+...+jn-in

Вы упоминаете в комментариях, что это правильно, но очень медленно.

В Java вы можете получить длину String с помощью s.length() — это значение кэшируется в объекте, и его нужно получить O(1).

Но когда вы переходите к C, вы получаете длину строки с strlen(s), которая каждый раз пересчитывается (в O(n)). Итак, пока вы должны делать O(n), поскольку у вас есть операция O(n), вся функция становится O(n^2).

Чтобы обойти это, кэшируйте значение один раз при его запуске. Это вернет вас в линейное время.

Плохой:

scanf("%s",s);
for(i=0;i<strlen(s);i++)
    if(s[i]==s[0])
    {
        sum=sum+getSim(s,i);
    }

Хорошо:

scanf("%s",s);
strlen = strlen(s); /* assume you declared "int strlen" earlier */
for(i=0;i<strlen;i++) /* this is now constant time to run */
    if(s[i]==s[0])
    {
        sum=sum+getSim(s,i);
    }