后缀数组的python模拟--编程珠玑 15.2

qmya00

　　

今天看了编程珠玑第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, a[i+M]) > maxlen) {
maxlen = comlen(a, 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,a[i+1])>maxlen:
maxlen=comlen(a,a[i+1])
maxi=a
print maxi
print c[maxi:maxi+maxlen+1]
 






测试：

还是书上banana的例子：

结果：ana

再来一个：acbc bcd

结果：bc