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 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #define MAXN 300005*2 #define INF -200000000 //0x80000000 using 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]
         
          =2 && p1
          
           =1 && p2