LRS с использованием программы C - PullRequest
Новая
       28

LRS с использованием программы C

2 голосов
/ 27 января 2020

Итак, я хочу создать функцию, используя C, чтобы найти самую длинную повторяющуюся не перекрывающуюся подстроку в данной строке. Например: ввод банана. Вывод:

Я думал об использовании массива строки и проверке повторов. Это жизнеспособный подход? Как бы я мог сравнить подстроки с остальными строками. Я хочу по возможности избегать суффиксных деревьев 

#include <stdio.h>
#include <string.h>

void stringcheck(char a[],int len, int s1, int s2)
{

    int i=s1+1;
    int j=s2+1;
    if(j<=len&&a[i]==a[j])
    {
        printf("%c",a[i]);
        stringcheck(a,len,i,j);
    }

}
void dupcheck(char a[], int len, int start)
{
    for(int i=start;i<len-1;i++)
    {
       for(int j=i+1;j<=len;j++)
       {
           if(a[i]==a[j])
           {
               printf("%c",a[i]);
               stringcheck(a,len,i,j);
               i=len;
           }

       }
    }
}


int main()
{
    char input[99];
    scanf("%s",input);
    int start=0;
    int len =strlen(input);
    dupcheck(input,len,start);
    return 0;

}

1 Ответ

3 голосов
/ 27 января 2020

Да, это правильный подход.
Вы можете сравнивать строку - символ за символом, поэтому нет необходимости действительно сохранять подстроку.

Вы можете увидеть динамическое c решение с использованием c ++, использующее этот подход здесь: https://www.geeksforgeeks.org/longest-repeating-and-non-overlapping-substring/
Это решение может быть преобразовано в c без особых изменений.

Другой вариант, если опция заключается в том, чтобы сохранить подстроку по ее индексам.
Затем можно сравнить ее со строкой и сохранить максимальную подстроку, однако для этого потребуется O (n ^ 3), когда вышеупомянутое решение делает это в O (n ^ 2).

редактировать: я преобразовал решение в c: 

#include <stdio.h>
#include <string.h>

void longestRepeatedSubstring(char * str, char * res) 
{ 
    int n = strlen(str);
    int LCSRe[n+1][n+1];
    int res_length  = 0; // To store length of result
    int i, j, index = 0;

    // Setting all to 0 
    memset(LCSRe, 0, sizeof(LCSRe)); 

    // building table in bottom-up manner 
    for (i=1; i<=n; i++) 
    { 
        for (j=i+1; j<=n; j++) 
        { 
            // (j-i) > LCSRe[i-1][j-1] to remove 
            // overlapping 
            if (str[i-1] == str[j-1] && 
                LCSRe[i-1][j-1] < (j - i)) 
            { 
                LCSRe[i][j] = LCSRe[i-1][j-1] + 1; 

                // updating maximum length of the 
                // substring and updating the finishing 
                // index of the suffix 
                if (LCSRe[i][j] > res_length) 
                { 
                    res_length = LCSRe[i][j]; 
                    index = (i>index) ? i : index; 
                } 
            } 
            else
                LCSRe[i][j] = 0; 
        } 
    } 

    // If we have non-empty result, then insert all 
    // characters from first character to last 
    // character of string
    j=0;
    if (res_length > 0) {
        for (i = index - res_length + 1; i <= index; i++) {
            res[j] = str[i-1];
            j++;
        }
    }
    res[j]=0;
} 

// Driver program to test the above function 
int main() 
{ 
    char str[] = "banana";
    char res[20];
    longestRepeatedSubstring(str, res);
    printf("%s",res); 
    return 0; 
}
...