http://www.lydsy.com/JudgeOnline/problem.php?id=4650

http://uoj.ac/problem/219

这里有非常好的题解qwq

接着道题复习一下模板(还是打错了好多地方_(:з」∠)_)

以及后缀数组面对多组数据清数组的正确打开方式qwq

因为求height数组时依赖n之后的字符都为空,倍增算法利用sa计算第一关键字时也依赖n之后的关键字都为空。

所以应至少在字符串第n+1位清空来终止可能会越界的求height数组的函数。还要把存第一关键字和第二关键字下标的数组都清空qwq

还是这种设关键点+差分的\(O(n\ln n)\)的方法也是一个经典模板。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 30013; int t1[N], t2[N], c[N]; void st(int *x, int *y, int *sa, int n, int m) {
for (int i = 0; i <= m; ++i) c[i] = 0;
for (int i = 0; i < n; ++i) ++c[x[y[i]]];
for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
for (int i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
} void mkhz(int *r, int *sa, int n, int m) {
memset(t1, 0, sizeof(t1));
memset(t2, 0, sizeof(t2));
int *x = t1, *y = t2, *t, i, j, p;
for (i = 0; i < n; ++i) x[i] = r[i], y[i] = i;
st(x, y, sa, n, m);
for (j = 1, p = 1; j < n && p < n; j <<= 1, m = p - 1) {
for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
st(x, y, sa, n, m);
for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j] ? p - 1 : p++;
}
} void mkh(int *r, int *sa, int *rank, int *h, int n) {
h[0] = 0; int k = 0, j;
for (int i = 0; i < n; ++i) rank[sa[i]] = i;
for (int i = 1; i < n; h[rank[i++]] = k)
for (k ? --k : k = 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; ++k);
} void pref(int *h, int f[N][16], int n) {
for (int i = 1; i < n; ++i) f[i][0] = h[i];
for (int j = 1; (1 << j) < n; ++j)
for (int i = (1 << j); i < n; ++i)
f[i][j] = min(f[i][j - 1], f[i - (1 << (j - 1))][j - 1]);
} char s1[N], s2[N];
int r1[N], r2[N], f1[N][16], f2[N][16], sa1[N], sa2[N], h1[N], h2[N];
int Log_2[N], rank1[N], rank2[N], n, sum_pre[N], sum_suf[N]; int lcp(int i, int j) {
i = rank1[i]; j = rank1[j];
if (i > j) i ^= j ^= i ^= j;
int l = Log_2[j - i];
return min(f1[j][l], f1[i + (1 << l)][l]);
} int lcs(int i, int j) {
i = rank2[n - i + 1]; j = rank2[n - j + 1];
if (i > j) i ^= j ^= i ^= j;
int l = Log_2[j - i];
return min(f2[j][l], f2[i + (1 << l)][l]);
} int main() {
int cnt = 0;
for (int i = 1; i <= 30000; ++i) {
if ((1 << (cnt + 1)) <= i) ++cnt;
Log_2[i] = cnt;
}
int T; scanf("%d", &T);
while (T--) {
scanf("%s", s1 + 1);
n = strlen(s1 + 1);
for (int i = 1, j = n; i <= n; ++i, --j)
r2[j] = r1[i] = s1[i] - 'a' + 1;
r1[n + 1] = r2[n + 1] = 0;
mkhz(r1, sa1, n + 1, 26);
mkh(r1, sa1, rank1, h1, n + 1);
mkhz(r2, sa2, n + 1, 26);
mkh(r2, sa2, rank2, h2, n + 1);
pref(h1, f1, n + 1);
pref(h2, f2, n + 1); memset(sum_pre, 0, sizeof(int) * (n + 1));
memset(sum_suf, 0, sizeof(int) * (n + 1));
int x, y, l, r;
for (int len = 1; (len << 1) <= n; ++len)
for (int i = 1, j; (j = i + len) <= n; i = j) {
x = lcs(i, j);
y = lcp(i, j);
if (x + y - 1 >= len) {
++sum_pre[max(j, j + len - x)];
--sum_pre[min(j + len, j + y)];
++sum_suf[max(i - len + 1, i - x + 1)];
--sum_suf[min(i + 1, i + y - len + 1)];
}
} for (int i = 1; i <= n; ++i) {
sum_pre[i] += sum_pre[i - 1];
sum_suf[i] += sum_suf[i - 1];
} ll ans = 0;
for (int i = 2; i <= n; ++i)
ans += 1ll * sum_pre[i - 1] * sum_suf[i];
printf("%lld\n", ans);
}
return 0;
}

最新文章

  1. Android 权限列表
  2. 第一章 Android系统移植与驱动开发概述
  3. ButterKnife--View注入框架
  4. 解决Gmail/GCalendar图标丢失问题
  5. ASP.NTE 5 Target framework dnx451 and dnxcore50(转)原文:http://www.cnblogs.com/xishuai/p/aspnet5-target-framework-dnx451-and-dnxcore50.html
  6. 关于 ActiveMQ 的消息模式
  7. iOS 使用FMDB SQLCipher给数据库加密
  8. [课程相关]homework-07
  9. linux安装mysql出现Could NOT find Curses (missing CURSES_LIBRARY CURSES_INCLUDE_PATH),提示解决方法
  10. WildFly 9.0.2 启用 SSL
  11. iOS_SN_详解沙河(转载)
  12. [Android]Eclipse的使用
  13. Pycharm集成PyQt4并使用
  14. js 操作 cookie
  15. 用户不在sudoers 文件中。此事将被报告 or (usermod:“sudo”组不存在)
  16. 浅析HSTS
  17. java-16习题
  18. 向后台提交数据:cookie,secure_cookie,
  19. day11(python)装饰器
  20. matlab数学实验--第二章

热门文章

  1. Yii2实现读写分离(MySQL主从数据库)
  2. HDU 2717 Catch That Cow (深搜)
  3. TOJ 1005 Hero In Maze (深搜)
  4. this的九种常用场景(转子jb51.net)
  5. HTML JS文字闪烁实现(项目top.htm分析)
  6. 【VI Script】你不知道的脚本编程
  7. C# 笔记——索引器
  8. google fcm 推送的流程
  9. 【mongo】用户添加、导入数据库、连接VUE
  10. ES6的新增数据类型:Symbol