Ural 1517. Freedom of Choice 后缀数组-白红宇

Ural 1517. Freedom of Choice 后缀数组

阅读量：4575 次

发布时间：2019-06-08

本文共 946 字，大约阅读时间需要 3 分钟。

所谓后缀数组，实际上准确的说，应该是排序后缀数组。

一个长度为N的字符串，显然有N个后缀，将他们放入一个数组中并按字典序排序就是后缀数组的任务。

这个数组有很好的性质，使得我们运行一些算法时可以大幅度的优化。

本题就是后缀数组的一个主要应用，快速求得后缀S（i）和S（j）的最长公共前缀LCP。

**由字典序的性质可知 S（i）和S（j）的LCP长度就是 h[sa[i]+1],h[sa[i]+2].... h[sa[j]]中的最小值，证明显然。

**而如何计算h数组呢？有一个性质 h[rank[i]]>=h[rank[i-1]]-1. 由两两对应关系可以证明（同时去掉首字符）。

代码如下后缀数组并不复杂

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const int MAXN=200000+100;void radix(int *str,int *a,int *b,int n,int m){ static int count[MAXN]; memset(count,0,sizeof(count)); for(int i=0;i
             
              =0;--i)b[--count[str[a[i]]]]=a[i];}void sorted_suffix_array(int *str,int *sa,int n,int m){ static int rank[MAXN],a[MAXN],b[MAXN]; for(int i=0;i
              
               
                =n? 0:rank[j+(1<
                
                 ans&&(sa[i-1]
                 
                  
                   >n; string a,b; cin>>a>>b; work(a,b); return 0;}