今天看了编程珠玑第15章字符串的前两节,对于后缀数组这玩意很感兴趣(以前学的太少了),对于15.2节的求给定文本输入的最长重复子串的问题,顺着作者的思路和其网站( http://netlib.bell-labs.com/cm/cs/pearls/index.html )上的代码,用c语言实现了一下,网站上代码如下:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int pstrcmp(char **p, char **q)
{ return strcmp(*p, *q); }
int comlen(char *p, char *q)
{ int i = 0;
while (*p && (*p++ == *q++))
i++;
return i;
}
#define M 1
#define MAXN 5000000
char c[MAXN], *a[MAXN];
int main()
{ int i, ch, n = 0, maxi, maxlen = -1;
while ((ch = getchar()) != EOF) {
a[n] = &c[n];
c[n++] = ch;
}
c[n] = 0;
qsort(a, n, sizeof(char *), pstrcmp);
for (i = 0; i < n-M; i++)
if (comlen(a[i], a[i+M]) > maxlen) {
maxlen = comlen(a[i], a[i+M]);
maxi = i;
}
printf("%.*s\n", maxlen, a[maxi]);
return 0;
}
后缀数组很强大哈!
但是,可以看到,后缀数组使用的是指针,如果在python这种没有指针的语言中该怎么用呢?答案是数组。
于是做了python的简单模拟,代码如下:
def pstrcmp(p,q):
return cmp(c[p:],c[q:])
def comlen(p,q):
j=0
while j<len(c[p:])-1 and c[p:][j]==c[q:][j]:
j=j+1
return j
c=''
a=[]
maxlen=-1
maxi=0
c=raw_input()
for i in range(len(c)):
a.append(i)
a.sort(pstrcmp)
for i in range(len(a)-1):
if comlen(a[i],a[i+1])>maxlen:
maxlen=comlen(a[i],a[i+1])
maxi=a[i]
print maxi
print c[maxi:maxi+maxlen+1]
测试:
还是书上banana的例子:
结果:ana
再来一个:acbc bcd
结果:bc
分享到:
相关推荐
ASP.NET.2.0.编程-------珠玑ASP.NET.2.0.编程-------珠玑ASP.NET.2.0.编程-------珠玑ASP.NET.2.0.编程-------珠玑
编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码
我觉得不错,和大家分享! 编程珠玑 编程珠玑 编程珠玑
编程珠玑编程珠玑
ASP.NET 2.0编程珠玑--来自MVP的权威开发指南
《编程珠玑(续)》是计算机科学方面的经典名著《编程珠玑》的姊妹篇,讲述了对于程序员有共性的知识。书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例,这些内容组成一个有机的整体,...
---------------------------------------- 编程珠玑第2版源码
编程珠玑和编程珠玑续两本,上传赚点分,填充填充填充
编程珠玑续、编程珠玑续本、编程珠玑续本、编程珠玑续本
编程珠玑II(编程珠玑·续) 扫描版6.56M pdf格式
中文第二版-编程珠玑,很不错的东西中文第二版-编程珠玑,很不错的东西
《编程珠玑》第一版是我早期职业生涯中阅读过的对我影响较大的书籍之一,在书中首次接触到的很多观点都让我长期受益。作者在这一版本中做了重要更新。新增加的很多例子让我耳目一新。 ——Steve McConnell,《代码...
编程珠玑,编程珠玑续以及源码,本书针对程序设计人员探讨了一系列的实际问题,这些问题是对现实中常见问题的归纳总结。作者虽然没有给出解决这些问题的具体代码,但始终非常富有洞察力和创造力地围绕着这些折磨...
编程珠玑(第二版)答案
编程珠玑是一本提升coding能力不可多得的好书,看书时,可以结合这个笔记,突出重点。
《编程珠玑(第 2版·修订版)》是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者JonBentley以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员...
这本书是《编程珠玑》高清pdf,如有侵权请告知。