LRS使用C程序

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。

另一个变体，如果选项是通过其索引保存子字符串。
然后您可以将它与字符串进行比较，并保存最大子字符串，但是当上述解决方案在 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; 
}

LRS使用C程序

LRS using C program

c

string-comparison

longest-substring