欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-01-10 17:38:14
...

今天看了编程珠玑第15章字符串的前两节,对于后缀数组这玩意很感兴趣(以前学的太少了后缀数组的python模拟--编程珠玑 15.2 
            
    
    博客分类: Python算法 后缀数组编程珠玑python ),对于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