hdu3518 Boring counting(后缀数组)

Myth丶恋晨 2023-08-17 17:21 138阅读 0赞

# Boring counting #

[题目传送门][Link 1]

## 解题思路 ##

后缀数组。枚举每种长度，对于每个字符串，记录其最大起始位置和最小起始位置，比较是否重合。

## 代码如下 ##

#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int N = 1005; char s[N]; int sa[N], x[N], y[N], c[N]; int n, m; void get_sa() { for(int i = 1; i <= m; i ++) c[i] = 0; for(int i = 1; i <= n; i ++) c[x[i] = s[i]] ++; for(int i = 1; i <= m; i ++) c[i] += c[i - 1]; for(int i = n; i >= 1; i --) sa[c[x[i]] --] = i; for(int k = 1; k <= n; k <<= 1){ int num = 0; for(int i = n - k + 1; i <= n; i ++) y[++num] = i; for(int i = 1; i <= n; i ++) if(sa[i] > k) y[++num] = sa[i] - k; for(int i = 1; i <= m; i ++) c[i] = 0; for(int i = 1; i <= n; i ++) c[x[i]] ++; for(int i = 1; i <= m; i ++) c[i] += c[i - 1]; for(int i = n; i >= 1; i --) sa[c[x[y[i]]] --] = y[i], y[i] = 0; swap(x, y); num = 1; x[sa[1]] = num; for(int i = 2; i <= n; i ++){ if(sa[i] + k <= n && sa[i - 1] + k <= n) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])? num: ++num; else x[sa[i]] = ++num; } if(num == n) break; m = num; } } int height[N], rk[N]; void get_h() { int k = 0; for(int i = 1; i <= n; i ++) rk[sa[i]] = i; for(int i = 1; i <= n; i ++){ if(rk[i] == 1) continue; if(k) --k; int j = sa[rk[i] - 1]; while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k; height[rk[i]] = k; } } int main() { while(scanf("%s", s + 1) != EOF && s[1] != '#'){ n = strlen(s + 1); m = 'z'; get_sa(); get_h(); ll ans = 0; for(int k = 1; k <= n / 2; k ++){ int maxx, minn; maxx = sa[1], minn = sa[1]; for(int i = 2; i <= n; i ++){ if(height[i] < k){ if(maxx - minn >= k) ++ans; maxx = sa[i], minn = sa[i]; } else { maxx = max(maxx, sa[i]); minn = min(minn, sa[i]); } } if(maxx - minn >= k) ++ ans; } printf("%lld\n", ans); } return 0; }

转载于:https://www.cnblogs.com/whisperlzw/p/11420486.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=3518