poj 3581 后缀数组 详解

本文主要是介绍poj 3581 后缀数组 详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个题折腾了快一个月，终于今晚又奋战了4个小时，AC掉了

题目：http://poj.org/problem?id=3581

首先看我写这个后缀数组教程，其实还不错http://blog.csdn.net/u011026968/article/details/20851295

关于第一个位置，反向读入，然后求后缀数组，找最小位置就好

第二个位置比较麻烦，参考这个博客的例子：http://bbezxcy.iteye.com/blog/1420546

大致思路：

    由于需要翻转，所以在输入时就按照反序输入。比如样例输入是5     10 1 2 3 4。我们从后向前读入就变为5     4 3 2 1 10。对这列数求出后缀数组。在大于2的后最中找到最小的后缀并输出。对于剩下的前缀s，我们把s串接到自己后面，也就是ss。再对这个串求出后缀数组，然后再把s中最小的前缀输出。最后把剩下的串输出。

 

对于第二步为什么要复制剩余串接在后面，用下面案例说明

6

10 1 2 2 3 4

 

第一步翻转后得到

4 3 2 2 1 10

 

求出后缀数组后得到最小的后缀便是：1 10，将其输出

剩下来的串是 4 3 2 2.

 

我们如果直接从剩余串中找到最小后缀的话会产生以下结果。

最小后缀是 2，输出。

输出剩余串 4 3 2。

最后得到1 10 2 4 3 2  很明显是wrong的

 

 

我们把剩余的串复制到剩余串的后面。

对 4 3 2 2 4 3 2 2求出后缀数组。

得到前四个字符的最小的后缀是 2 2，输出。

输出剩余串 4 3.

得到1 10 2 2 4 3 

 

这里解释了为啥不能直接对剩下的串求后缀数组

我个人除了很多问题，，，，我再想想做个总结，随后附上

/*******************************************************/
//POJ 3581 后缀数组   by Pilgrim
//注意:1、此代码中k是全局变量 别乱用
//     2、algorithm
//     3、注意此题的字典序的定义，跟往常不一样的
//     4、因为有负数所以最小的应该是int的下限而不是0
/******************************************************/#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>#define MAXN 300005*2
#define INF -200000000
//0x80000000using namespace std;int n,k,pp,mm;
int num[MAXN],rr[MAXN];
int Rank[MAXN],tmp[MAXN],sa[MAXN];bool cmpSa(int i, int j)
{if(Rank[i]!=Rank[j]){return Rank[i]<Rank[j];}else{int ik = i+k<=n?Rank[i+k]:-INF-1;int jk = j+k<=n?Rank[j+k]:-INF-1;return ik<jk;}
}bool cmpSa2(int i, int j)
{if(Rank[i]!=Rank[j]){return Rank[i]<Rank[j];}else{int ik = i+k<=pp?Rank[i+k]:-INF-1;int jk = j+k<=pp?Rank[j+k]:-INF-1;return ik<jk;}
}bool cmpSS(int i,int j)
{return rr[i]<rr[j];
}void con_sa(int s,int e)
{int i,j;//sort(tmp+s,tmp+e+1,cmpSS);for(i=s;i<=e;i++)Rank[i]=rr[i];Rank[e]=INF;//printf("%d tmp=%d rank=%d\n",i,tmp[i],Rank[tmp[i]]);/*此时的rank已经能表示相对大小*/for(k=1;k<=e;k*=2){if(mm){pp=e;sort(sa+s,sa+e+1,cmpSa2);}else{sort(sa+s,sa+e+1,cmpSa);}tmp[sa[s]]=s;for(i=s+1;i<=e;i++){tmp[sa[i]]=tmp[sa[i-1]]+(cmpSa(sa[i-1],sa[i])?1:0);}for(i=s;i<=e;i++)Rank[i]=tmp[i];}
}void show(int p1,int p2)
{for(int i=p1;i<n;i++)printf("%d\n",num[i]);for(int i=p2;i<p1;i++)printf("%d\n",num[i]);for(int i=0;i<p2;i++)printf("%d\n",num[i]);
}void Init()
{memset(tmp,0,sizeof(tmp));memset(Rank,0,sizeof(Rank));memset(sa,0,sizeof(sa));for(int i=0;i<n;i++){scanf("%d",&num[i]);rr[n-i-1] = num[i];/*rr是整个反转后的串,*/sa[i]=i;}sa[n]=n;for(int i=0;i<=n;i++){num[i]=rr[i];tmp[i]=i;}
}void Init2(int e)
{memset(tmp,0,sizeof(tmp));memset(Rank,0,sizeof(Rank));memset(sa,0,sizeof(sa));for(int i=0;i<e;i++){rr[i+e] = rr[i];}for(int i=e*2;i<=2*n;i++)rr[i]=INF;for(int i=0; i<=e*2; i++){sa[i]=tmp[i]=i;tmp[i]=i;}
}int main()
{//freopen("poj 3581.txt","r",stdin);int p1,p2;scanf("%d",&n);mm=0;Init();con_sa(0,n);for(int i=0;i<=n;i++){p1=sa[i];if(p1>=2 && p1<n)break;}mm=1;Init2(p1);con_sa(0,p1*2);for(int i=0; i<=p1*2;i++){p2=sa[i];if(p2>=1 && p2<p1)break;}show(p1,p2);return 0;
}

这篇关于poj 3581 后缀数组 详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---