后缀数组笔记

网上很多后缀数组的资料,但是都过于难,至少我是没有看懂的.历经了几个月,今天再度重温,有点柳暗花明又一村的感觉

先看看一个大家都看的懂的程序

 

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h> 

#define MAXCHAR 5000 //最长处理5000个字符

char c[MAXCHAR], *a[MAXCHAR];

int comlen(char *p, char *q)
{
    int i = 0;
    while(*p && (*p++ == *q++))
        ++i;
    return i;
}

/**
  * 比较字符串
  */

int pstrcmp(const void *p1, const void *p2)
{
    return strcmp(*(char* const *)p1, *(char* const*)p2);
}

int main()
{
    char ch;
    int n = 0;
    int i, temp;
    int maxlen = 0, maxi = 0;
    printf("Please input your string:\n");

    while((ch = getchar()) != '\n')
    {
        a[n] = &c[n];
        c[n++] = ch;
    }

    c[n] = '\0';

    for(i=0;i<n;i++)
      printf("%d:%s\n", i+1, a[i]);
    

   qsort(a, n, sizeof(char*), pstrcmp);

    for(i=0;i<n;i++)
    printf("%d:%s\n", i+1, a[i]);
    

   for(i = 0; i < n - 1 ;++i)
    {
        temp = comlen(a[i], a[i+1]);
        if(temp > maxlen)
        {
            maxlen = temp;
            maxi = i;
        }
    }
    printf("%.*s\n",maxlen, a[maxi]);

    system("PAUSE");

    return 0;

}



这里这个qsort你可以自己写个,本人比较懒!!其实qsort后,a[i]就是排好序的了.交换a[i]的时候,如果再指定一个数组sa[i]=i+1, qsort后sa[]数组也就求出了!!!!我这里没用这么高深的东东. 我上面的解法由于只求最长重复子串就省去了height数组,节约空间!!!当然这个做法的效率是不敢恭维的,仅仅用来理解后缀数组!!!

 Height[i] = comlen(a[i], a[i+1]);  0<=i

例 1 ：最长公共前缀
给定一个字符串，询问某两个后缀的最长公共前缀。   // 直接套用，        ans=min(height[i])    k

例 2 ：可重叠最长重复子串
给定一个字符串，求最长重复子串，这两个子串可以重叠。   // ans=max(height[i])  0<=i

例 3 ：最长回文子串
将整个字 符串反过来写在原字符串后面，中间用一个特殊的字符隔开。这样就把问题变为 了
求这个新的字符串的某两个后缀的最长公共前缀。
eg：abcbaebf ---->   abcbaebf &fbeabcba