洛谷P3809 后缀排序【后缀数组】【模板】-白红宇

洛谷P3809 后缀排序【后缀数组】【模板】

阅读量：5275 次

发布时间：2019-06-14

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

题目背景

这是一道模板题。

题目描述

读入一个长度为

输入输出格式

输入格式：

一行一个长度为

输出格式：

一行，共n个整数，表示答案。

输入输出样例

输入样例#1：

ababa

输出样例#1：

5 3 1 4 2

说明

$10^6n<=106$

后缀数组知识点详解：

https://www.cnblogs.com/wyboooo/p/9854468.html

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             10 using namespace std;11 typedef long long LL;12 #define inf 0x7f7f7f7f13 14 const int maxn = 1e6 + 5;15 char s[maxn];16 int n;17 int sa[maxn];18 int t1[maxn], t2[maxn], c[maxn];19 int rnk[maxn], height[maxn];20 21 void build_sa(char s[], int n, int m)22 {23 int i, j, p, *x = t1, *y = t2;24 for(i = 0; i < m; i++)c[i] = 0;25 for(i = 0; i < n; i++)c[x[i] = s[i] - '0']++;26 for(i = 1; i < m; i++)c[i] += c[i - 1];27 for(i = n - 1; i >= 0; i--)sa[--c[x[i]]] = i;28 for(j = 1; j <= n; j <<= 1){29 p = 0;30 for(i = n - j; i < n; i++)y[p++] = i;31 for(i = 0; i < n; i++)if(sa[i] >= j) y[p++] = sa[i] - j;32 for(i = 0; i < m; i++)c[i] = 0;33 for(i = 0; i < n; i++)c[x[y[i]]]++;34 for(i = 1; i < m; i++)c[i] += c[i - 1];35 for(i = n - 1; i >= 0; i--)sa[--c[x[y[i]]]] = y[i];36 swap(x, y);37 p = 1;38 x[sa[0]] = 0;39 for(i = 1; i < n; i++)40 x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j] ? p - 1:p++;41 if(p >= n)break;42 m = p;43 }44 }45 46 int main()47 {48 scanf("%s", s);49 n = strlen(s);50 build_sa(s, n, 200);51 printf("%d", sa[0] + 1);52 for(int i = 1; i < n; i++){53 printf(" %d", sa[i] + 1);54 }55 printf("\n");56 return 0;57 }