后缀数组的python模拟--编程珠玑 15.2
今天看了编程珠玑第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, *a;
int main()
{ int i, ch, n = 0, maxi, maxlen = -1;
while ((ch = getchar()) != EOF) {
a = &c;
c = ch;
}
c = 0;
qsort(a, n, sizeof(char *), pstrcmp);
for (i = 0; i < n-M; i++)
if (comlen(a, a) > maxlen) {
maxlen = comlen(a, a);
maxi = i;
}
printf("%.*s\n", maxlen, a);
return 0;
}
后缀数组很强大哈！
但是，可以看到，后缀数组使用的是指针，如果在python这种没有指针的语言中该怎么用呢？答案是数组。
于是做了python的简单模拟，代码如下：
def pstrcmp(p,q):
return cmp(c,c)
def comlen(p,q):
j=0
while j<len(c)-1 and c==c:
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)>maxlen:
maxlen=comlen(a,a)
maxi=a
print maxi
print c
测试：
还是书上banana的例子：
结果：ana
再来一个：acbc bcd
结果：bc
页:
[1]