使用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(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);
               break;
           }

       }
    }
}


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）。

Answer 2

我可能会选择这样的东西：

char* lrs(char *s)
{
    size_t length = strlen(s);
    for (size_t len = length / 2; len > 0; len--)
        for (size_t i = 0; i <= length - 2 * len; i++)
            for (size_t j = i + len; j <= length - len; j++)
                if (0 == strncmp(&s[i], &s[j], len))
                {
                    // could also alloc a new buffer
                    s[i + len] = '\0';
                    return &s[i];
                }

    // no common substrings found
    return NULL;
}