【あはは、アルゴリズム】の10、接尾辞の配列、最長の繰り返しのサブ列を求めます

変換元:http://blog.csdn.net/hackbuteer1/article/details/7968623
直感的な解法は,まず長さn−1の文字列を検出し,繰返しがなければn−2を検出し,1まで減少する.
この方法の時間的複雑さはO(N＊N＊N)であり,長さ緯度,長さに基づいて検出された文字列数,文字列検出の3つの部分を含む.
接尾辞配列接尾辞配列はデータ構造であり、1つの文字列に対して対応する接尾辞配列を生成した後、並べ替え、隣接する2つの文字列の先頭共通部分を順番に検出する.このような時間的複雑度は、接尾辞配列O(N)を生成し、ソートO(NlogN*N)の最後尾のNは、文字列比較もO(N)が隣接する2つの文字列O(N*N)を順次検出するためであり、総時間的複雑度はO(N^2*logN)であり、第1の方法のO(N^3)よりも優れている
demoは以下の通りです.
ここで、comlen関数パラメータとしての2つの文字列の長さが等しい場合、関数は最初の文字からこの長さ値を返します.

int comlen( char *p, char *q )  
{  
    int i = 0;  
    while( *p && (*p++ == *q++) )  
        ++i;  
    return i;  
}  

int main(void)  
{  
    int i , j , thislen , maxlen = -1;  
    ......  
    ......  
    ......  
    for(i = 0 ; i < n ; ++i )  
    {  
        for(j = i+1 ; j < n ; ++j )  
        {  
            if((thislen = comlen(&c[i] , &c[j])) > maxlen)  
            {  
                maxlen = thislen;  
                maxi = i;  
                maxj = j;  
            }  
        }  
    }  
    ......  
    ......  
    ......  
    return 0;  
}  

完全なコードは次のとおりです.

#include <iostream>  
using namespace std;  
  
#define MAXCHAR 5000 //    5000     
  
char c[MAXCHAR], *a[MAXCHAR];  
  
int comlen( char *p, char *q )  
{  
    int i = 0;  
    while( *p && (*p++ == *q++) )  
        ++i;  
    return i;  
}  
  
int pstrcmp( const void *p1, const void *p2 )  
{  
    return strcmp( *(char* const *)p1, *(char* const*)p2 );  
}  
  
  
int main(void)  
{  
    char ch;  
    int  n=0;  
    int  i, temp;  
    int  maxlen=0, maxi=0;  
    printf("Please input your string:
");  
  
    n = 0;  
    while( (ch=getchar())!='
' )  
    {  
        a[n] = &c[n];  
        c[n++] = ch;  
    }  
    c[n]='\0';     //    c             ，          
  
    qsort( a, n, sizeof(char*), pstrcmp );  
    for(i = 0 ; i < n-1 ; ++i )  
    {  
        temp=comlen( a[i], a[i+1] );  
        if( temp>maxlen )  
        {  
            maxlen=temp;  
            maxi=i;  
        }  
    }  
    printf("%.*s
",maxlen, a[maxi]);  
      
    return 0;  
}  

要素a[0]は文字列全体を指し、次の要素は2番目の文字で始まる配列の接尾辞などを指す.入力文字列が「banana」の場合、配列はこれらの接尾辞を表します.
a[0]:banana
a[1]:anana
a[2]:nana
a[3]:ana
a[4]:na
a[5]:a
配列aのポインタは文字列の各接尾辞を指すため、配列aを「接尾辞配列」と命名する
接尾辞配列をすばやく並べ替えて、接尾辞に近い(変位語)サブストリングをまとめてqsort(a,n,sizeof(char*)、pstrcmp)後a[0]:a[1]:ana[2]:anna a[3]:banana a[4]:na a[5]:nana
comlen関数を使用して配列をスキャンして隣接要素を比較し、最も長い重複文字列を見つけます.
2つ目の方法はkmpアルゴリズム、next配列による方法です.

#include<iostream>  
using namespace std;  
  
const int MAX = 100000;  
int next[MAX];  
char str[MAX];  
  
void GetNext(char *t)  
{  
    int len = strlen(t);  
    next[0] = -1;  
    int i = 0 , j = -1;  
    while(i < len)  
    {  
        if(j == -1 || t[i] == t[j])  
        {  
            i++;  
            j++;  
            if(t[i] != t[j])  
                next[i] = j;  
            else  
                next[i] = next[j];  
        }  
        else  
            j = next[j];  
    }  
}  
int main(void)  
{  
    int i , j , index , len;  
    cout<<"Please input your string:"<<endl;  
  
    cin>>str;  
    char *s = str;  
    len = 0;  
    for(i = 0 ; *s != '\0' ; s++ , ++i)  
    {  
        GetNext(s);  
        for(j = 1 ; j <= strlen(s) ; ++j)  
        {  
            if(next[j] > len)  
            {  
                len = next[j];  
                index = i + j;    //index          str       
            }  
        }  
    }  
    if(len > 0)  
    {  
        for(i = index - len ; i < index ; ++i)  
            cout<<str[i];  
        cout<<endl;  
    }  
    else  
        cout<<"none"<<endl;  
  
    return 0;  
}  

abcdefgegcsgcasseのような最も長い重複しないサブ列を求めて、最も長い重複しないサブ列はabcdefgで、長さは7です

#include <iostream>
#include <list>
using namespace std;

//  ：              。 i j         。
//          ，  +1；         ，  +1，                   ，  i
//            -1。    ，  '\0'
int find(char str[],char *output)
{
	int i = 0 , j = 0;
	int cnt[26] = {0};
	int res = 0 , temp = 0;
	char *out = output;
	int final;
	while(str[j] != '\0')
	{
		if(cnt[str[j]-'a'] == 0)
		{
			cnt[str[j]-'a']++;

		}
		else
		{
			cnt[str[j]-'a']++;
			while(str[i] != str[j])
			{	
				cnt[str[i]-'a']--;
				i++;
			}
			cnt[str[i]-'a']--;
			i++;
		}	

		j++;
		temp = j-i;
		if(temp > res)
		{
			res = temp;
			final = i;
		}
	}
	//     output  
	for(i = 0 ; i < res ; ++i)
		*out++ = str[final++];
	*out = '\0';
	return res;
}
int main(void)
{
	char a[] = "abcdefg";
	char b[100];
	int max = find(a,b);
	cout<<b<<endl;
	cout<<max<<endl;
	return 0;
}