さいちょうくりかえしさぶれつもんだい

今日の面接は見たことのない問題に、すっかり退屈になった.1段の文字列の最も長い繰り返しのサブ列を求めます.後でネット上でブログを見て、意外にもKMPで書くことができて、自分の無知のために恥ずかしいと感じます.では、KMPでこのような問題を解決する方法を学びましょう.肝心なのはnextの特性でこの問題を解決することです.

#include <iostream>

#include <cstring>

using namespace std;

int Get_next(char *p, int nextval[])

{

    int j = -1;

    nextval[0] = -1;

    int len = strlen(p);

    int i = 0;

    int maxlen = 0;

    while(i < len)

    {

        if(j == -1 || p[i] == p[j])

        {

            i++;

            j++;

            nextval[i] = j;

            if(j > maxlen)   //              ，             

                maxlen = j;

        }

        else

            j = nextval[j];

    }

    return maxlen;

}



int main()

{

    char s[100];

    cin >> s;

    int maxlen = 0;//      

    int nextMax; //Get_next        

    int i;

    int maxIndex;

    int len = strlen(s);

    for(i = 0; i < len-1; i++)

    {

        int *next = new int[len - i];

        nextMax = Get_next(s + i, next);

        if(nextMax > maxlen)

        {

            maxIndex = i;

            maxlen = nextMax;

        }

    }

    cout << "        ：" << endl;

    for(i = 0; i < maxlen; i++)

        cout << s[i + maxIndex];

    cout << endl;

}

KMPの特性を使ってこの問題を解決するには、時間の複雑さが少し高いでしょう.
物事にはいつも解決策があるので,接尾辞配列というデータ構造がこの方法を解決する.1つの文字列に対して対応する接尾辞配列を生成した後、並べ替え、並べ替えた後、隣接する2つの文字列の先頭部分を順次検出します.

#include <iostream>

#include <cstring>

#include <stdio.h>

#include <algorithm>

using namespace std;

#define MAXLEN 10000

char str[MAXLEN], *arr[MAXLEN];



int CalLen(const char *str1, const char *str2)

{

    int len = 0;

    while(*str1 && (*str1++ == *str2++))

        len++;

    return len;

}



int pStrCmp(const void *str1, const void *str2)

{

    return strcmp(*(const char **)str1, *(const char **)str2);

}



int main()

{

    char ch;

    int n = 0;

    int maxlen = 0, maxIndex = 0;

    int temp;

    while((ch = getchar()) != '
')

    {

        arr[n] = &str[n];

        str[n++] = ch;

    }

    str[n] = '\0';

    qsort(arr, n, sizeof(char *), pStrCmp);

    for(int i = 0; i < n - 1; i++)

    {

        temp = CalLen(arr[i], arr[i + 1]);

        if(temp > maxlen)

        {

            maxlen = temp;

            maxIndex = i;

        }

    }

    cout << arr[maxIndex] << endl;;

}