poj2774 SA后缀数组

前言

SA后缀数组的典型应用，height数组求解最长公共子串

一、题目

题目链接: poj2774

二、思路及代码 1.思路

还是常规思路，先建立SA和height 然后求最长公共子串

2.代码

代码如下：

#include 
#include 
#include 
using namespace std;
const int maxn = 1e6;
int n, m;
char s[maxn], s1[maxn], s2[maxn];
int sa[maxn], rk[maxn], height[maxn];
int sa2[maxn], oldrk[maxn], tank[maxn];
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