后缀数组学习笔记

未分类

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
//#define ivorysi
#define MAXN 20005
using namespace std;
typedef long long ll;
int ra[MAXN],sa[MAXN];
int n,num[MAXN],str[MAXN],tmpa[MAXN],tmpb[MAXN],val[MAXN],sum[MAXN],height[MAXN];
bool cmp(int *arr,int s,int t,int l) {
    return arr[s] == arr[t] && arr[s + l] == arr[t + l];
}
void suffix(int len,int sc) {
    int *tmpra = tmpa,*tmpsa = tmpb;
    for(int i = 1 ; i <= sc ; ++i) sum[i] = 0;
    for(int i = 1 ; i <= len ; ++i) ++sum[tmpra[i] = str[i]];
    for(int i = 1 ; i <= sc ; ++i) sum[i] += sum[i - 1];
    for(int i = len ; i >= 1 ; --i) sa[sum[str[i]]--] = i;
    int all = 0;
    for(int j = 1 ; all < len ; j *= 2 , sc = all) {
    int l = 0;
    for(int k = len - j + 1 ; k <= len ; ++k) tmpsa[++l] = k;
    for(int k = 1 ; k <= len ; ++k) if(sa[k] > j) tmpsa[++l] = sa[k] - j;
    for(int k = 1 ; k <= len ; ++k) val[k] = tmpra[tmpsa[k]];
    for(int k = 1 ; k <= sc ; ++k) sum[k] = 0;
    for(int k = 1 ; k <= len ; ++k) sum[val[k]]++;
    for(int k = 1 ; k <= sc ; ++k) sum[k] += sum[k - 1];
    for(int k = len ; k >= 1 ; --k) sa[sum[k]--] = tmpsa[k];
    swap(tmpra,tmpsa);
    tmpra[sa[1]] = 1;
    for(all = 1 , int k = 2 ; k <= len ; ++k) 
        tmpra[sa[k]] = cmp(tmpsa,sa[k],sa[k - 1],j) ? all : ++all;
    sc = all;
    }
    for(int i = 1 ; i <= len ; ++i) ra[sa[i]] = i;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(scanf("%d",&n)) {
    for(int i = 1 ; i <= n ; ++i) scanf("%d",&num[i]);
    for(int i = 1 ; i < n ; ++i) str[i] = num[i + 1] - num[i] + 89;
    str[n] = 1;
    suffix(n,180);
    for(int i = 1 ; i < n ; ++i) {
        int k = max(height[i - 1] - 1,1);
        while(i + k <= n && sa[ra[i] - 1] + k <= n && str[i + k] == str[sa[ra[i] - 1] + k]) ++k;
        height[i] = k;
    }
    int l = 0 , r = n;
    while(l < r) {
        int mid = (l + r) >> 1;
    }
    }
}