使用C程序的LRS

Question

所以我想用C创建一个函数，在给定的字符串中找到最长的重复的、不重叠的子字符串。例如:输入香蕉。产出: an.

我正在考虑使用字符串数组的比较和检查重复。这是可行的方法吗？如何将子字符串与其他字符串进行比较。如果可能，我希望避免使用后缀树。

#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;

}

Answer 1

是的，这是一个有效的方法。

您可以逐字符比较字符串，这样就不需要真正保存子字符串了。

您可以在这里看到一个使用c++的动态解决方案：https://www.geeksforgeeks.org/longest-repeating-and-non-overlapping-substring/

此解决方案可以转换为c，而不需要进行多次更改。

另一个变体，如果该选项是通过它的索引保存子字符串。

然后，您可以将它与字符串进行比较，并保存max子字符串，但是当上面的解决方案在O(n^2)中这样做时，这将采用O(n^3)。

编辑:我将解决方案转换为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; 
}