poj3261 SA+二分

前言 一、题目

题目链接: poj3261

二、思路与代码 1.思路

年轻人AC的第一道SA题目 学了一个星期的后缀数组和后缀自动机，做出的第一道SA题，感动 这道题目挺典型的 建立SA、Height数组，然后对Height进行二分

2.代码

代码如下：

#include 
#include 
using namespace std;
const int maxn = 1e5 + 4;
const int inf = 0x3f3f3f3f;
int n, m, kk;
int s[maxn];
int sa[maxn], rk[maxn], height[maxn];
int sa2[maxn], oldrk[maxn], tank[maxn * 10];
bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
void rsort() {
  for (int i = 1; i