乐曲主题Musical Themes
2024-09-08 07:17:54
SA例题
对于串 \(S\) 的两个子串 \(A\) 和 \(B\) ,满足 \(k = |A| = |B|\),\(\exists c \forall i\, a_i + c=b_i\),且 \(A\) 和 \(B\) 在原串中没有重叠,求最大的满足条件的 \(k\)
先考虑 \(\forall i\, a_i=b_i\) 的情况,二分 \(k\) ,如果在\(height\)上存在一段满足 \(\forall L \le i \le R \,height_i\ge k\),且存在 \(SA[p_1]-SA[p_2] \ge k\),说明 \(k\) 满足条件
接下来将上述做法用在原数组的差分数组上即可,注意判定时条件要改为\(SA[p_1]-SA[p_2] > k\),且要在第一个字符前添加特殊字符,否则判定时可能出问题
#include<cstdio>
using namespace std;
const int MAXN = 5001;
int str[MAXN], sa[MAXN], rank[MAXN], ht[MAXN], buc[MAXN];
void Swap(int*& a, int*& b){
int *tmp = a; a = b; b = tmp;
}
void getSA(int s[], int len){
int *rk = rank, *tp = ht;
int crd = 180, p;
for (int i = 1; i <= len; ++i)
rk[i] = s[i], tp[i] = i;
for (int i = 0; i <= crd; ++i)
buc[i] = 0;
for (int i = 1; i <= len; ++i)
++buc[rk[i]];
for (int i = 1; i <= crd; ++i)
buc[i] += buc[i - 1];
for (int i = len; i >= 1; --i)
sa[buc[rk[tp[i]]]--] = tp[i];
for (int w = 1; p != len; w <<= 1, crd = p){
p = 0;
for (int i = len - w + 1; i <= len; ++i)
tp[++p] = i;
for (int i = 1; i <= len; ++i)
if (sa[i] > w)
tp[++p] = sa[i] - w;
for (int i = 0; i <= crd; ++i)
buc[i] = 0;
for (int i = 1; i <= len; ++i)
++buc[rk[i]];
for (int i = 1; i <= crd; ++i)
buc[i] += buc[i - 1];
for (int i = len; i >= 1; --i)
sa[buc[rk[tp[i]]]--] = tp[i];
Swap(rk, tp);
rk[sa[1]] = p = 1;
for (int i = 2; i <= len; ++i)
rk[sa[i]] = tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w] ? p : ++p;
}
for (int i = 1; i <= len; ++i)
rank[sa[i]] = i;
}
void getHeight(int s[], int len){
ht[1] = 0;
for (int i = 1, j = 0, pos; i <= len; ++i, --j){
if (rank[i] == 1)
continue;
if (j < 0)
j = 0;
pos = sa[rank[i] - 1];
while (s[i + j] == s[pos + j] && i + j <= len && pos + j <= len)
++j;
ht[rank[i]] = j;
}
}
bool judge(int k, int len){
int lp, rp;
for (int i = 1, j; i < len;){
if (ht[i + 1] >= k){
lp = rp = sa[i];
j = i + 1;
while (ht[j] >= k && j <= len){
if (sa[j] < lp)
lp = sa[j];
if (sa[j] > rp)
rp = sa[j];
++j;
}
if (rp - lp > k)
return 1;
i = j;
}
else
++i;
}
return 0;
}
int main(){
int slen;
scanf("%d", &slen);
for (int i = 1, pre = 89, tmp; i <= slen; ++i){
scanf("%d", &tmp);
str[i] = tmp - pre + 89; pre = tmp;
}
getSA(str, slen);
getHeight(str, slen);
int L = 1, R = slen >> 1, mid;
while (L + 1 < R){
mid = L + R >> 1;
if (judge(mid, slen))
L = mid;
else
R = mid;
}
int ans;
if (judge(R, slen))
ans = R;
else
ans = L;
if (ans < 4)
printf("0");
else
printf("%d", ans + 1);
return 0;
}
最新文章
- arch+xfce4系统配置
- mac版本cornerstone的无限期破解方法【转】
- *HDU 1237 栈
- C# 提供两种切割圆形图片的方式
- JS数组随机排序
- MSP430F149学习之路——按键
- System.Runtime.InteropServices.COMException (0x800706BA) 解决方法
- 安装apk文件报waiting for device 时解决办法
- linux 下 epoll 编程
- Median of Two Sorted Arrays (找两个序列的中位数,O(log (m+n))限制) 【面试算法leetcode】
- 浅析嵌入式Linux系统的构成和启动过程
- Appium键盘操作
- Shell错误[: missing `]&#39;
- java虚拟机学习-JVM内存管理:深入Java内存区域与OOM(3)
- vue有关小知识
- 同主机下Docker+nginx+tomcat负载均衡集群搭建
- Shell自学二(参数传递和数组)
- Spark2.1.0安装
- 廖雪峰Java1-4数组操作-5命令行参数
- [应用篇]第三篇 JSP 标准标签库(JSTL)总结