10253.cpp

本代码是在KMP算法上加以改进后

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

//求next函数
void GetNext(const char* T, int* next);
//求next函数，改良版
void BetterGetNext(const char* T, int* next);
//求S中第一个最长重复子串及其位置
void findLSub(const char* S, int *LSubLen, int *pos);
//返回n个int数中最大的一个
int findmax(int *array, int n, int* index);

int main(int argc, char* argv[])
{
    char *S = "bbbcccaaa";
    int LSubLen, pos, i;
    int *next = (int*)malloc(sizeof(int) * strlen(S));

    //BetterGetNext(S, next);
    //GetNext(S, next);
    findLSub(S, &LSubLen, &pos);

    printf("STRING S = %s\n", S);
    printf("it's longest sub string ...LSubLen = %d, pos = %d\n", LSubLen, pos);
    for(i = 0; i < LSubLen; i++)
        printf("%c", *(S+pos-1+i));
    printf("\n");
    free(next);
}

void GetNext(const char* T, int* next)
{
    int i = 0, j = -1;
    if(T[i])
        next[i] = j;
    else
        return;

    while(T[i+1] != 0)
    {
        if((j == -1) || (T[i] == T[j]))
        {
            i++; j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

void BetterGetNext(const char* T, int* next)
{
    int i = 0, j = -1;
    if(T[i])
        next[i] = j;
    else
        return;

    while(T[i+1] != 0)
    {
        if((j == -1) || (T[i] == T[j]))
        {
            i++; j++;
            if(T[i] == T[j])
                next[i] = next[j];
            else
                next[i] = j;
        }
        else
            j = next[j];
    }
}

//求S中一个最长重复子串长度及其位置
void findLSub(const char* S, int *LSubLen, int *pos)
{
    int i = 0, maxk, index, len = strlen(S);
    int *next = (int *)malloc(sizeof(int)*len);

    *LSubLen = 0;
    for(; i < len - 2;i++)
    {
        GetNext(S+i, next);
        maxk = findmax(next, len-i, &index);
        if(maxk > *LSubLen)
        {
            *LSubLen = maxk;//最长重复子串长度
            if((index == len) && (*(S+len-1) == *(S+i+*LSubLen)))//如最长重复子串的最后一个字符即串最后一个字符..且此字符与前面相同
                *LSubLen+=1;
            *pos = i + 1;//最长重复子串起始位置
        }
    }
    free(next);
}

//返回n个int数中最大的一个
int findmax(int *array, int n, int* index)
{
    int max = array[0];
    while( n > 0)
    {
        if(array[n-1] > max)
        {
            *index = n;
            max = array[n-1];
        }
        n--;
    }

    return max;
}