c语言解决最长重复子串问题

1.解题思路

最大后缀方法思路：

1. 用字符串指针数组保存用户输入的字符串的所有后缀字符串；

2. 将后缀字符串集合进行排序；

3. 比较相邻字符串的公共子串长度，找到长度最大值，保存相应字符串即为所求

2.源码实现

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

/*最长重复子串*/

#define MAXCHAR 2048

typedef short (*cmpfun)(char *a, char *b);

/*求出两个字符串的公共子串长度*/
int comlen(char *p, char *q)
{
    int i = 0;

    while(*p && (*p++  == *q++))
    {
        ++i;
    }

    return i;
}

/*求出两个字符串的公共子串*/
int comstr(char *p, char *q, char *c)
{
    int i = 0;

    while(*p && (*p == *q))
    {
        c[i] = *p;
        p++;
        q++;
        i++;
    }

    c[i] = 0x00;

    return i;
}

/*用字符串指针保存所有后缀字符串*/
int initpoint(char *c, char **a)
{
    int i;

    for(i=0; c[i]!=0x00; i++)
    {
        a[i] = &c[i];
    }

    a[i] = NULL;

    return i;
}

void bubsort(char **a, int n, cmpfun f)
{
    char *t;
    int i, j;

    for(i=0; i<n-1; i++)
    {
        for(j=0; j<n-1-i; j++)
        {
            if(f(a[j], a[j+1]) > 0)
            {
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
    }
}

short wecmp(char *a, char *b)
{
    return strcmp(a, b);
}

int main()
{
    char *a[MAXCHAR];
    char c[MAXCHAR];
    char d[MAXCHAR];
    int n;
    int i;
    int temp;
    int maxlen = 0;
    int maxi = 0;

    memset(d, 0x00, sizeof(d));

    scanf("%s", c);

    n = initpoint(c, a);

    /*for(i=0; i<n; i++)
    {
        printf("a[%d]=%s\n", i, a[i]);
    }*/

    /*将后缀字符串集合进行排序*/
    bubsort(a, n, wecmp);

    for(i=0; i<n-1; ++i)
    {
        temp = comlen(a[i], a[i+1]);

        /*printf("temp=%d\n", temp);
        printf("maxlen=%d\n", maxlen);
        printf("i=%d\n", i);
        printf("maxi=%d\n", maxi);*/

        if(temp > maxlen)
        {
            maxlen = temp;
            maxi = i;
        }
    }

    /*for(i=0; i<n; i++)
    {
        printf("a[%d]=%s\n", i, a[i]);
    }*/

    comstr(a[maxi], a[maxi+1], d);

    printf("%d\n", comlen(a[maxi], a[maxi+1]));
    printf("%s\n", d);

    return 0;
}

3.编译源码

$ gcc -o example examle.c -std=c89

4.运行及其结果

$ ./example
abcabc
3
abc