Question

C语言的简单题，求助大神！！

题目内容：
给定一个字符串，输出最长的重复子串，如有并列依此输出，如果没有则输出No output

输入格式:

一个字符串

输出格式：

最长的重复子串

输入样例：

as soon as

输出样例：

as

输入样例：

abcd

输出样例：

No output

时间限制：500ms内存限制：32000kb

Answer 1

#include <stdio.h>

struct s
{
    char *cp;    /*记录子串起始位置*/
    int cnt;    /*子串出现次数*/
    int len;    /*子串长度*/
    struct s *next;
};
int main(void)
{
    char s[1000];
    char *sp, *wp;
    struct s *head, *tail, *p;
    int max = 0;

    gets(s);
    sp = s;
    head = tail = NULL;
    while(*sp != '\0')
    {
        for(; *sp == ' '; *sp++ = '\0');    /*把子串前空格都改为'\0'结束字符*/
        wp = sp;    /*子串起始位置*/
        for(; *sp != ' ' && *sp != '\0'; *sp++);    /*找到子串结束位置*/
        if(wp != sp)    /*子串不为空*/
        {
            *sp = '\0';    /*为了输出方便，子串后填'\0'字符*/
            for(p = head; p; p = p->next)    /*寻找是否有已找到的相同子串记录*/
            {
                if(strcmp(wp, p->cp) == 0)
                {
                    p->cnt++;    /*如果有，该记录出现次数增加*/
                    if(p->len > max)
                        max = p->len;    /*判断该重复出现子串长度是否为最大，是则更新最大长度*/
                    break;
                }
            }
            if(p == NULL){    /*如果没有找到相同子串记录*/
                p = (struct s *)malloc(sizeof(struct s));    /*申请节点*/
                p->cnt = 1;
                p->len = strlen(wp);
                p->cp = wp;
                p->next = NULL;
                if(head == NULL)    /*挂载到连表上*/
                    head = p;
                else
                    tail->next = p;
                tail = p;
            }
        }
        sp++;
    }

    while(head)
    {
        p = head;
        head = head->next;
        if(p->cnt > 1 && p->len == max)    /*把重复出现的，长度为max的子串输出*/
            printf("%s\n", p->cp);
        free(p);    /*释放记录节点*/
    }

    if(max == 0)    /*如果max为0，说明没找到重复出现子串*/
        printf("No output\n");

    return 0;
}

Answer 2

那么问题来了，两个重复则子串允不允许有交集？比如：
abcd abcd abc
可以看到从第5个字符开始abcd abc 重复了那么结果就是7
如果不允许重复，那么答案就是abcd 结果就是4
我的方法是这样的，以每个字符开始，且将下一个字符与该字符组成一个子串作试探，因为字串至少有两个字符，找出和该子串相同的位置，若未找到，则字符位置增加重复上述过程，若找到，将找到的位置和原位置也就是最外层循环那个变量作为字串匹配的两个点，一个一个字符的扫描，找出不同的时候的位置，然后将所得的原位置，最长位置，以及其差值保存下来，重复上述过程，若寻找到的差值更长，则保存新的信息，直到每个字符全部扫描完成输出结果。