后缀数组

推荐学习方法

算法竞赛入门经典训练指南

简介

后缀数组把所有的后缀排序（基数排序），通过sa数组，rank，height数组来完成一系列关于子串的操作

主要运用

1 求不相同子串个数

SPOJ Distinct Substrings

n ( n + 1 ) / 2 − s u m ( h e i g h t [ 1 ] , h e i g h t [ 2 ] . . . h e i g h t [ n − 1 ] )

2018牛客多校（第一场）I Substring

题意：求一个字符串求所有不同构子串的个数，字符串仅有a,b,c
分析：比较本题与上一题，发现多了一个同构的限制，本字符串内的子串可能有同构的情况，首先想到的方法是除去同构，发现比较难实现，反其道而行之，枚举所有的同构情况，然后除以同构函数的个数6，就可以求出答案，注意特判单个字符的同构。

  1. 例题:

    1. 1031: [JSOI2007]字符加密Cipher 2.