Сходство строк в c - PullRequest
Новая
       25

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

1 голос
/ 15 января 2012

Для двух строк A и B мы определяем сходство строк как длину самого длинного префикса, общего для обеих строк.Например, сходство строк «abc» и «abd» равно 2, а сходство строк «aaa» и «aaab» - 3. Вычислить сумму сходств строки S с каждым из ее суффиксов

Вот мое решение ... 

#include<stdio.h>
#include<string.h>
int getSim(char str[],int subindex)
{
    int l2=subindex
    int i=0;
    int count=0;
    for(i=0;i<l2;i++)
        if(str[i]==str[subindex])
        {
            count++;
            subindex++;
        }
        else
            break;
    return count;   
}
int main()
{
    int testcase=0;
    int len=0;
    int sum=0;
    int i=0;
    char s[100000];
    scanf("%d",&testcase);
    while(testcase--)
    {
        sum=0;
        scanf("%s",s);
        for(i=0;i<strlen(s);i++)
            if(s[i]==s[0])
            {
                sum=sum+getSim(s,i);
            }
        printf("%d\n",sum);
    }
}

Как мы можем решить эту проблему, используя суффиксный массив ??

Ответы [ 2 ]

2 голосов
/ 15 января 2012

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

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

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

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

  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

1 голос
/ 15 января 2012

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

В 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);
    }
...