后缀数组整理

总感觉自己运用后缀数组能力不够啊，先整理一下之前我做过的后缀数组的题目吧

先上基本模板（倍增）

 readln(s);
    n:=length(s);
    fillchar(sum,sizeof(sum),0);
    for i:=1 to n do
    begin
      y[i]:=ord(s[i]);
      inc(sum[y[i]]);
    end;
    m:=255;
    for i:=2 to m do
      inc(sum[i],sum[i-1]);
    for i:=n downto 1 do
    begin
      sa[sum[y[i]]]:=i;
      dec(sum[y[i]]);
    end;
    p:=1;
    rank[sa[1]]:=1;
    for i:=2 to n do
    begin
      if y[sa[i]]<>y[sa[i-1]] then inc(p);
      rank[sa[i]]:=p;
    end;
    m:=p;
    j:=1;
    while m<n do     //后缀完成排序必然是每一个名次对应唯一的后缀
    begin
      y:=rank;
      fillchar(sum,sizeof(sum),0);
      p:=0;
      for i:=n-j+1 to n do      //第一关键字排序
      begin
        inc(p);
        x[p]:=i;
      end;
      for i:=1 to n do
        if sa[i]>j then
        begin
          inc(p);
          x[p]:=sa[i]-j;
        end;
      for i:=1 to n do
      begin
        rank[i]:=y[x[i]];    //在第一关键字的基础上对第二关键字排序
        inc(sum[rank[i]]);
      end;
      for i:=2 to m do
        inc(sum[i],sum[i-1]);
      for i:=n downto 1 do
      begin
        sa[sum[rank[i]]]:=x[i];
        dec(sum[rank[i]]);
      end;
      p:=1;
      rank[sa[1]]:=1;
      for i:=2 to n do
      begin
        if (y[sa[i]]<>y[sa[i-1]]) or (y[sa[i]+j]<>y[sa[i-1]+j]) then inc(p);
        rank[sa[i]]:=p;
      end;
      j:=j shl 1;    //倍增
      m:=p;
    end;
    h[1]:=0;    //求height数组（相邻名次的后缀的最长公共前缀，即LCP）
    p:=0;
    for i:=1 to n do
    begin
      if rank[i]=1 then continue;
      j:=sa[rank[i]-1];
      while s[i+p]=s[j+p] do inc(p);
      h[rank[i]]:=p;
      if p>0 then dec(p);  //根据h[i]>=h[i-1]-1的性质
    end;

 下面就是应用了

单字符串的：

bzoj1031 裸的后缀数组，把字符串在后面再接一个一样的，然后做一遍即可，根本没用到height

poj1743 男人八题之一（！！！），将数字预处理之后就是求不重叠的最长重复子串的长

        考虑到后缀之间的LCP一定是有重复的但不确定是否重叠

        根据罗大牛的方法，我们先二分答案，将问题转化为判定性问题，假设当前需要判定的答案为k

        接着我们根据后缀名次的顺序分组，如果height[i]>=k 则suffix(sa[i])和suffix(sa[i-1])在一组，否则不在

        这样我们就保证，同组内的后缀，任意两个后缀的LCP>=k

       （因为根据height数组性质，LCP(i,j)=min(h[rank[i]+1]~h[rank[j]) （假定rank[i]<rank[j])

        接着，只要这组内有两个后缀，他们起始位置之差>=k，就一定存在一个不小于k的不重叠重复子串

        （LCP保证重复出现，起始位置差>=k 保证必有一个>=k的LCP不重叠

        这样我们只要在分组的过程找一下这组内后缀起始位置的最大最小值就行了，总的复杂度O(nlogn) 

        注意这道题有些特殊要求

poj3261 求出现最少k次的最长重复子串（可重叠）

        同上题，二分，分组，如果一个组内有k个后缀则为可行解

poj3623 这题使用后缀数组来优化贪心

        贪心很好想，我之前也讲过

        选取对于剩余串中头尾i,j ，要判断s[i..j]小还是其倒序小

        表面上看是前缀和后缀的比较，实际上，我们把原串反序添加在原串后面（少不了的分隔符）

        在分隔符的帮助下，这样我们就可以转化为后缀和后缀的比较~

        注意不要PE了这题         

双（多）字符串：

一般对于双（多）字符串的题目，我们考虑将字符串合并成一个串

串之间加一个分隔符来区分

poj2774 经典了，最长公共子串，合并串，扫一遍height 

        找到两个名次相邻后缀分列不同的串的height最大值即可

        但会不会存在height[k] sa[k]和sa[k-1]在同一个串呢 影响到最优值呢 

        假设存在，要想影响最优值，必然得有

        LCP（i,j）=height[k] i,j在不同串，

        根据性质LCP(i,j)=min(height[rank[i]+1]~height[rank[j]])=height[k]

        则 1.height[rank[i]+1]~height[rank[j]]>=height[k]

        因为i，j在不同串，则在rank[i]~rank[j]中，必然存在相邻两个后缀在不同串

        并且他们的LCP>=k (根据1） 则sa[k]和sa[k-1]在同一个串的height[k]一定不会影响到最优解

        

bzoj3172 问每个串i在合并后的串出现了多少次

         等价于 有多少个后缀j，使得LCP(i,j)>=length(s[i])

         毫无疑问，要用RMQ预处理区间最小值（这里的区间是建立在名次上的，简单说就是height的区间最小值）

         然后我们分类讨论rank>rank[i]的后缀和rank<rank[i]的后缀

         以rank[j]∈[1,rank[i]]的后缀为例，不难发现

         随着rank[j]越靠近rank[i],则他们的LCP与有可能>=length(s[i]) （ 根据LCP和height的关系）

         当LCP(j,i)>=length(s[i])的时候，rank[k]∈(rank[j],rank[i])的后缀k和i的LCP也一定>=length(s[i])

         决策具有单调性~！于是当然的二分答案（找临界）

         最后把两种情况答案情况加起来即可）

在这里提醒，在多个字符串用后缀数组处理的时候，一定要把数组开大一些，注意多个字符串之间不同的分隔符）