标签：family 最大 考过 总结 close mat 就会 bit 后缀
出大问题，我原来学了几天，然后刷了七八题吧，之后将近半年一次没用到， 今天回头一想后缀数组？？？？？？？？？？
所以来总结一下，省的模板题都不会了。
rk[i] 第i个后缀的排名; SA[i] 排名为i的后缀位置; Height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP
1 POJ - 3261:找出出现k次的可重叠的最长子串的长度。 https://vjudge.net/contest/283743#problem/D
思路：直接二分次数就行了，在判断里面看是连续>=k的最多有几个。
#include
#include
#include
#include
#include #define ll long long
#define rep(i, a, b) for(int i = a; i #define pb push_back
#define mp make_pair
using namespace std;
const int mod = 1e9 + 7;
const ll INF = 1e15;
const double eps = 1e-8;
const int maxn = 2e5 + 10;
int sa[maxn],rk[maxn], height[maxn], h[maxn], y[maxn], x[maxn], c[maxn];
int n, m;
int s[maxn];
void get_sa(){
int tt;
rep(i, 1, n) c[x[i] = s[i]]++;
rep(i, 2, m) c[i] += c[i - 1];
for(int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
//基数排序
for(int k = 1; k 1){
int num = 0;
for(int i = n - k + 1; i i;
rep(i, 1, n) if(sa[i] > k) y[++num] = sa[i] - k;
rep(i, 0, m) c[i] = 0;
rep(i, 1, n) c[x[i]]++;
rep(i, 2, m) c[i] += c[i - 1];
for(int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
rep(i, 0, n) {
tt = x[i];
x[i] = y[i];
y[i] = tt;
}
x[sa[1]] = 1, num = 1;
rep(i, 2, n) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
if(num == n) break;
m = num;
}
}
void get_height(){
int k = 0;
rep(i, 1, n) rk[sa[i]] = i;
rep(i, 1, n){
if(rk[i] == 1) continue;
if(k) k--;//h[i] >= h[i - 1] - 1
int j = sa[rk[i] - 1];
while(j + k ;
height[rk[i]] = k;
}
}
bool judge(int len, int k){
int have = 1;
rep(i, 2, n){
if(height[i] >= len) have++;
else have = 1;
if(have >= k) return 1;
}
return 0;
}
int main(){
int k; scanf("%d%d",&n, &k);
m = 1e5;
rep(i, 1, n){
scanf("%d",&s[i]);
m = max(m, ++s[i]);
}
get_sa();
get_height();
int l = 1, r = n;
int ans = 1;
while(l r){
int mid = (l+r) / 2;
if(judge(mid, k)){
ans = mid;
l = mid+1;
}
else r = mid-1;
}
cout endl;
return 0;
}
View Code
2 SPOJ - DISUBSTR:不同子串的个数。 https://vjudge.net/contest/283743#problem/E
思路：所有的子串和是(n+1)*n/2，我们现在还需要个重复的个数，这样总的减去重复的就是我们要的。考虑height数组含义，和上一后缀的最长公共前缀的长度。
举个例子：
后缀sa[i-1]: aaabbd
后缀 sa[i] : aabbd
重复的是aa,现在我们要减去aa有多少个不同的子串，然后你发现这个重复的一定是同一个字母，不可能出现aaaab这种情况，因为这是后缀，你可以随便试试。这种串的子串个数就等于串的长度，也就是height。
那么答案出来了ans = (n+1)*n/2 - height[2 ~ n]; 因为height[1]是排名1的与上一位的最长公共前缀，所以它前边都没有。
#include #define ll long long
#define rep(i, a, b) for(int i = a; i #define pb push_back
#define mp make_pair
using namespace std;
const int mod = 1e9 + 7;
const ll INF = 1e15;
const double eps = 1e-8;
const int maxn = 2e3 + 10;
int sa[maxn],rk[maxn], height[maxn], h[maxn], y[maxn], x[maxn], c[maxn];
int n, m;
char s[maxn];
void get_sa(){
int tt;
rep(i, 0, m) c[i] = 0;
rep(i, 1, n) c[x[i] = s[i]]++;
rep(i, 2, m) c[i] += c[i - 1];
for(int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
//基数排序
for(int k = 1; k 1){
int num = 0;
for(int i = n - k + 1; i i;
rep(i, 1, n) if(sa[i] > k) y[++num] = sa[i] - k;
rep(i, 0, m) c[i] = 0;
rep(i, 1, n) c[x[i]]++;
rep(i, 2, m) c[i] += c[i - 1];
for(int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
rep(i, 0, n){
tt = x[i];
x[i] = y[i];
y[i] = tt;
}
x[sa[1]] = 1, num = 1;
rep(i, 2, n) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
if(num == n) break;
m = num;
}
}
void get_height(){
int k = 0;
rep(i, 1, n) rk[sa[i]] = i;
rep(i, 1, n){
if(rk[i] == 1) continue;
if(k) k--;//h【i】 >= h[i - 1] - 1
int j = sa[rk[i] - 1];
while(j + k ;
height[rk[i]] = k;
}
}
int main(){
int t; scanf("%d",&t);
while(t--){
scanf("%s", s + 1);
m = 122, n = strlen(s + 1);
get_sa();
get_height();
int ans = (n+1)*n / 2;
rep(i, 2, n) ans -= height[i];
printf("%d\n",ans);
}
return 0;
}
View Code
3 POJ - 2406:给出一个串，是由它的一个子串重复k次得到的，问k最大是多少。https://vjudge.net/contest/283743#problem/G
思路：第一种方法直接用next数组，求过next数组后直接输出 if(len % (len - ne[len]) == 0) printf("%d\n",len / (len-ne[len])); else printf("1\n");
第二种就是后缀数组，自己没写，不加了。
4 POJ - 2774:求两个串的最长公共子串。 https://vjudge.net/contest/283743#problem/J
思路：先用个分隔符将两个字符串连起来，对这个新串跑一遍后缀数组，找最大的height值，注意还要满足条件：sa[i]与sa[i-1]分别在两串字符中,这样就保证height是两个串的公共前缀。
#include
#include
#include
#include
#include #define ll long long
#define rep(i, a, b) for(int i = a; i #define pb push_back
#define mp make_pair
using namespace std;
const int mod = 1e9 + 7;
const ll INF = 1e15;
const double eps = 1e-8;
const int maxn = 2e5 + 10;
int sa[maxn],rk[maxn], height[maxn], h[maxn], y[maxn], x[maxn], c[maxn];
int n, m;
char s[maxn];
void get_sa(){
int tt;
rep(i, 0, m) c[i] = 0;
rep(i, 1, n) c[x[i] = s[i]]++;
rep(i, 2, m) c[i] += c[i - 1];
for(int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
//基数排序
for(int k = 1; k 1){
int num = 0;
for(int i = n - k + 1; i i;
rep(i, 1, n) if(sa[i] > k) y[++num] = sa[i] - k;
rep(i, 0, m) c[i] = 0;
rep(i, 1, n) c[x[i]]++;
rep(i, 2, m) c[i] += c[i - 1];
for(int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
rep(i, 0, n){
tt = x[i];
x[i] = y[i];
y[i] = tt;
}
x[sa[1]] = 1, num = 1;
rep(i, 2, n) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
if(num == n) break;
m = num;
}
}
void get_height(){
int k = 0;
rep(i, 1, n) rk[sa[i]] = i;
rep(i, 1, n){
if(rk[i] == 1) continue;
if(k) k--;//h【i】 >= h[i - 1] - 1
int j = sa[rk[i] - 1];
while(j + k ;
height[rk[i]] = k;
}
}
char st[maxn];
int main(){
scanf("%s %s",s+1,st+1);
int len1 = strlen(s+1);
int len2 = strlen(st+1);
n = len1+len2+1;
s[len1+1] = ‘#‘;
rep(i, 1, len2){
s[len1+i+1] = st[i];
}
// s[len1+len2+2] = 0;
n = strlen(s+1);
m = 122;
get_sa();
get_height();
int l, r;
int ma = 0;
rep(i, 2, n){
l = sa[i-1];
r = sa[i];
if(l continue;
else if(l > len1+1 && r > len1+1) continue;
else ma = max(ma, height[i]);
}
printf("%d\n",ma);
return 0;
}
View Code
5 POJ - 1743: https://vjudge.net/contest/283743#problem/C 不知道为啥当初学后缀数组时上来先写的这个，看了好久，现在思考过上边的几题后再想这个也很简单。
题意：有N(1 最长的重复主题。“主题”是整个音符序列的一个子串，它需要满足如下条件：
1、长度至少为5个音符。
2、在乐曲中重复出现。(可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值)
3、重复出现的同一主题不能有公共部分。
思路：这题需要解决的问题有：重复子串的长度，重复部分不能有重合，转调。先把会的先想出来，重复子串的长度直接用height判断，不能有重合直接用sa判断位置是否有重合。就差这个转调了。
序列每个音符都加上或者减去同一个整数值，这不得不想到差分，这样就很容易想到我们只需要把数组预处理成差分就行了，因为s[i] - s[i-1]可能有负数，这样求sa就会有问题，都加上个数让数组不为负就行了，因为这个最大是88，差值不会超过88，所以我就加了个88，不用纠结于此。以上问题都解决了，怎么得到最长的？肯定是二分啊，明显满足二分属性。
#include
#include
#include
#include
#include #define ll long long
#define rep(i, a, b) for(int i = a; i #define pb push_back
#define mp make_pair
using namespace std;
const int mod = 1e9 + 7;
const ll INF = 1e15;
const double eps = 1e-8;
const int maxn = 1e5 + 10;
int sa[maxn],rk[maxn], height[maxn], h[maxn], y[maxn], x[maxn], c[maxn];
//rk[i] 第i个后缀的排名; SA[i] 排名为i的后缀位置; Height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP
int n, m;
int s[maxn];
void get_sa(){
int tt;
rep(i, 0, n) c[i] = 0;
rep(i, 1, n) c[x[i] = s[i]]++;
rep(i, 2, m) c[i] += c[i - 1];
for(int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
//基数排序
for(int k = 1; k 1){
int num = 0;
for(int i = n - k + 1; i i;
rep(i, 1, n) if(sa[i] > k) y[++num] = sa[i] - k;
rep(i, 0, m) c[i] = 0;
rep(i, 1, n) c[x[i]]++;
rep(i, 2, m) c[i] += c[i - 1];
for(int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
rep(i, 0, n){
tt = x[i];
x[i] = y[i];
y[i] = tt;
}
x[sa[1]] = 1, num = 1;
rep(i, 2, n) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
if(num == n) break;
m = num;
}
}
void get_height(){
int k = 0;
rep(i, 1, n) rk[sa[i]] = i;
rep(i, 1, n){
if(rk[i] == 1) continue;
if(k) k--;
int j = sa[rk[i] - 1];
while(j + k ;
height[rk[i]] = k;
}
}
bool judge(int k){
int ma = sa[1], mi = sa[1];
rep(i, 2, n){
if(height[i] sa[i];
else{
mi = min(sa[i], mi);
ma = max(sa[i], ma);
if(ma - mi + 1 >= k) return 1;
}
}
return 0;
}
int main(){
while(scanf("%d",&n) && n){
rep(i, 1, n) scanf("%d",&s[i]);
m = 0;
rep(i, 1, n-1){
s[i] = s[i+1] - s[i] + 88;
m = max(m, s[i]);
}
s[n] = 0; n--;
get_sa();
get_height();
int l = 4, r = n/2;
int ans = 0;
while(l r){
int mid = (l+r) / 2;
if(judge(mid)){
ans = mid;
l = mid+1;
}
else r = mid-1;
}
// cout
if(ans >= 4) printf("%d\n",ans+1);
else printf("0\n");
}
return 0;
}
View Code
后缀数组模板题总结
标签：family 最大 考过 总结 close mat 就会 bit 后缀
原文地址：https://www.cnblogs.com/philo-zhou/p/13378949.html