Lang:G++
Edit12345678910111213141516171819202122232425262728293031#include <iostream>#include <cstdio>#include <cstdlib>#include <string>#include <map>#include <algorithm>#define MAX 20010#define MAXVALUE 0x3FFFFFFFusing namespace std;int N, K;string s, c;int SA[MAX];//后缀数组,保存排序后后缀字符串的开头位置,本身下标对应名次int RANK[MAX];//名次数组,保存排序后后缀字符串名次,本身下标对应字符串开头位置int HEIGHT[MAX];//排名相邻的两个后缀的最长公共前缀map<string, int>m;void solve(){int i, j;int index;m.clear();for (i = 1; i < N; ++i)m.insert(make_pair(s.substr(i, N - i), i));auto it = m.begin();for (i = 1; it != m.end(); ++it,++i){index = it->second;SA[i] = index;RANK[N - it->first.length()] = i;}