プログラミング珠玉(二)文字列の中で最も長い繰り返し文字列を探します

たとえば、文字列「banana」の最長重複文字列はanaです.ここでは簡単なデータ構造の文字列配列を使用します.実際には文字列ポインタ配列、char*タイプの配列で、文字アドレスで各文字を表し、スペースを節約できます.アルゴリズムは簡単で,各接尾辞配列を求め,その後接尾辞配列を並べ替え,最後に隣接する2つの配列間の最大共通文字列を求める.

#include <iostream>
using namespace std;

void common_str(char *s, char **com);
void bubble(char **a, int s, int e);
int common_len(const char *s1, const char *s2); // s1 s2                

int main()
{
        char s[] = "banana";
        char *com = NULL;
        common_str(s, &com);
        printf("common str is %s
", com);
        return 0;
}

void common_str(char *s, char **com)
{
        int len = strlen(s);
        char **a = new char *[len];
        int i = 0;
        while(s[i])
        {
                a[i] = &s[i];
                i++;
        }
        bubble(a, 0, len-1);

        int com_len = 0;
        char *com_str = NULL;
        for(int j=0; j<=len-2; j++)
        {
                int c_len = common_len(a[j], a[j+1]);
                if(c_len > com_len)
                {
                        com_len = c_len;
                        com_str = a[j];
                }
        }
        *com = new char[com_len + 1];
        memcpy(*com, com_str, com_len);
        (*com)[len] = '\0'; //          ，            NULL,      *com[len] = '\0';[]        *
}

void bubble(char **a, int s, int e)
{
        int len = e-s+1;
        for(int i = len-1; i--; i>0)
                for(int j = 0; j<=i; j++)
                        if(strcmp(a[j], a[j+1]) > 0)
                        {
                                char *temp = a[j];
                                a[j] = a[j+1];
                                a[j+1] = temp;
                        }

}

int common_len(const char *s1, const char *s2)
{
        int len = 0;
        while(*s1 == *s2 && s1!=NULL && s2!=NULL)
        {
                len++;
                s1++;
                s2++;
        }
        return len;

}