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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
能不能通俗的讲解下傅立叶分析和小波分析之间的关系?
作者:咚懂咚懂咚 链接:https://www.zhihu.com/question/22864189/answer/40772083 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 从傅里叶变换到小波变换,并不是一个完全抽象的东西,可以讲得很形象。小波变换有着明确的物理意义,如果我们从它的提出时所面对的问题看起,可以整理出非常清晰的思路。 下面
【转载】通俗的讲解下傅立叶分析和小波分析之间的关系?
【转载】通俗的讲解下傅立叶分析和小波分析之间的关系?作者:咚懂咚懂咚,稍有常识的人 来源:知乎专栏从傅里叶变换到小波变换,并不是一个完全抽象的东西,完全可以讲得很形象。小波变换有着明确的物理意义,如果我们从它的提出时所面对的问题看起,可以整理出非常清晰的思路。下面我就按照傅里叶–>短时傅里叶变换–>小波变换的顺序,讲一下为什么会出现小波这个东西、小波究竟是怎样的思路。(反正题主要求的是通俗形象,没
目前hadoop大数据的视频教程谁讲的比较好?我个人对比,欢迎评论补充
正在学习大数据,教材比较容易找hadoop权威指南就可以,大家一件比较统一。但是视频教程比较多,也没看到有公认比较突出的。所以我决定一点点看并把感想分享在这里。 1,马士兵老师的Hadoop教程以及相关大数据教程 我刚看完,实在斗鱼直播上进行的,所以含有大量冗余。但是作为入门教程是十分合适的。首先因为马士兵老师是个明白人,说话都准确干练,入门的思路也很简单。 看完这个教程可以搭建一个
今天经理给我讲了好多东西(spring mvc)
spring,mvc的一点小头绪
如何更好地给同事讲代码?
我们技术团队有两个习惯:一是程序员写好一个新的比较重要的系统,或是引入了一个第三方框架或库后,主程会要求程序员做一个ppt,在会议室里给所有程序与QC做一次团队分享;二是程序员写好一个新系统,或做了比较大的或比较重要的修改后,要知会相关QC,并把QC叫到电脑前,一对一把相关代码给QC讲一遍。     我认为做ppt团队分享可以起到两个重要作用:一是让团队成员之间时常互通有无,避免各人只了解自
设计模式(讲的比较好-思路清晰,非泛泛而谈)
设计模式(Design pattern)是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。 毫无疑问,设计模式于己于他人于系统都是多赢的,设计模式使代码编制真正工程化,设计模式是软件工程的基石,如同大厦的一块块砖石一样。项目中合理的运用设计模式可以完美的解决很多问题,每种模式在现在中都有相应的原理来与之对应,每
Python--第一天:谁来给我讲讲Python?
来源: http://blog.csdn.net/youmengdaigu/article/details/49668797 作为无基础的初学者,只想先大概了解一下Python,随便编个小程序,并能看懂一般的程序,那些什么Java啊、C啊、继承啊、异常啊通通不懂怎么办,于是我找了很多资料,写成下面这篇日记,希望以完全初学者的角度入手来认识Python这个在量化领
JAVA学习 孙鑫 张孝祥 韩顺平 马士兵?哪个老师讲的更好些
本文转自: 如:尚学堂J2SE是最好的,而JSP则MLDN的最好,至于servlet,则数韩顺平老师录制的了!关于框架,struts尚学堂讲得很不错,传智的还行,但过于理论化,不建议初学者, hibernate其实尚学堂与传智都不怎么样,刚入门的会听不太懂,但传智的比尚学堂的讲得要好一点,看一下书,再听听视频就可以了,尚学堂的hibernate给人的感觉有点逻辑不清楚 ,spring 用
推荐一个讲解设计模式的视频
演示语言是C#的
蓝牙讲解下--通信
名称解释 UUID 含义是通用唯一识别码 (Universally Unique Identifier),这 是一个软件建构的标准,也是被开源软件基金会 (Open Software Foundation, OSF) 的组织应用在分布式计算环境 (Distributed Computing Environment, DCE) 领域的一部分 Rfcomm 一个基于欧洲电信标准协会ETSI07.10规