2 duduniuang duduniuang 于 2014.12.13 11:24 提问

一个程序谁给讲解下?
for

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]);

}

2个回答

devmiao
devmiao   Ds   Rxr 2014.12.13 11:30
已采纳

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

子串:字符串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)

devmiao
devmiao   Ds   Rxr 2014.12.13 11:30
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!