后缀数组是一个字符指针数组，数组中指针所指的对象包含了字符串的每一个后缀，因此成为后缀数组。
看代码：
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <fstream>
#include <queue>
#include <ctime>
#include <set>
using namespace std;
#define MAXN 5000000
char c[MAXN],*a[MAXN];
bool cmp(char *p,char *q) //对后缀数组进行排序所用的谓词函数
{
return strcmp(p,q)<0;
}
int comlen(char *p,char *q) //计算最长公共子串的长度
{
int i=0;
while(*p && (*p++==*q++))i++;
return i;
}
int main()
{
char ch;
int n=0;
while((ch=getchar())!=EOF)
{
c[n]=ch;
a[n]=&c[n];
n++;
}
c[n]=' ';
sort(a,a+n,cmp);
//for(int i=0;i<n;i++)cout<<a[i]<<endl;
int maxlen=-1,maxi=0;
for(int i=0;i<n-1;i++)
{
if(comlen(a[i],a[i+1])>maxlen){
maxlen=comlen(a[i],a[i+1]);
maxi=i;
}
}
printf("%.*s
",maxlen,a[maxi]); //输出前maxlen个字符
return 0;
}
样例输入：ask not what your country can do for you,but what you can do for your country.
输出： “ can do for you”
由于排序的存在，算法需要O(n logn)的时间。