问题描述

一个程序谁给讲解下？

char * suff[100];

int pstrcmp(const void p, const void *q)
{
return strcmp((char**)p,*(char**)q);
}

int comlen_suff(char * p, char * q)
{
int len = 0;
while(*p && *q && *p++ == *q++)
{
++len;
if(*p == '#' || *q == '#')
{
return len;
}
}
return 0;
}

void LCS_suffix(char * X, int xlen, char * Y, int ylen)
{
int suf_index = maxlen = maxindex = 0;

int len_suff = xlen + ylen + 1;
char * arr = new char [len_suff + 1];  /* 将X和Y连接到一起 */
strcpy(arr,X);
arr[xlen] = '#';
strcpy(arr + xlen + 1, Y);

for(int i = 0; i < len_suff; ++i)  /* 初始化后缀数组 */
{
    suff[i] = & arr[i];
}

qsort(suff, len_suff, sizeof(char *), pstrcmp);

for(int i = 0; i < len_suff-1; ++i)
{
    int len = comlen_suff(suff[i],suff[i+1]);
    if(len > maxlen)
    {
        maxlen = len;
        suf_index = i;
    }
}
outputLCS(suff[suf_index]);

}

解决方案

后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也并不逊色，而且它比后缀树所占用的内存空间小很多。

子串：字符串S的子串r[i..j]，i<=j，表示r串中从i到j这一段，也就是顺次排列r[i],r[i+1],...,r[j]形成的字符串。

后缀：后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串 s 的从第i个字符开始的后缀表示为Suffix(i)， 也就是Suffix(i)=r[i..len(s)]。

大小比较：关于字符串的大小比较，是指通常所说的“字典顺序”比较，也就是对于两个字符串u、v，令i 从1 开始顺次比较u[i]和v[i]，如果u[i]=v[i]则令i加1，否则若u[i]v[i]则认为u>v（也就是vlen(u)或者i>len(v)仍比较不出结果，那么，若len(u)len(v)则u>v。
从字符串的大小比较的定义来看，S的两个开头位置不同的后缀u和v进行比较的结果不可能是相等，因为u=v的必要条件len(u)=len(v)在这里不可能满足。

后缀数组：后缀数组SA是一个一维数组，它保存1..n的某个排列SA[1]，SA[2]，……，SA[n]，并且保证Suffix(SA[i])<Suffix(SA[i+1])，1<=i<n。也就是将S的n个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA中。

1 后缀数组求最长公共子串（LCS）

解决方案二：

http://www.cnblogs.com/luxiaoxun/archive/2012/10/05/2712131.html