Cruiying

后缀数组

2-sat(1) BSGS(2) dfs(2) dp(63) dp + 线段树(1) floyd(3) Hash(1) KM算法(1) Kruskal重构树(2) LCA(6) manachar(2) Mendix(4) tarjan(1) 中位数(1) 主席树(2) 二分(3) 分数规划(3) 前缀和优化dp(2) 单调栈(6) 单调队列(1) 单调队列优化dp(1) 博弈(2) 字典树(1) 差分约束系统(1) 并查集(4) 异或(2) 思维(2) 思维题(4) 扩展欧几里得算法(1) 拉格朗日插值(2) 数论(8) 未归档(15) 构造(1) 枚举(1) 模拟(3) 模板(1) 水题(4) 矩阵加速(2) 线段树(3) 网络流(2) 莫比乌斯反演(2) 莫队(4) 蓝桥杯(1) 规律(2) 贪心(2) 输入输出(1) 题解(1)

/ 注册

全部文章 / 后缀数组（共15篇）

ccpc网络赛03（后缀数组+二分+倍增+主席树）

Problem DescriptionYou are given a string S consisting of only lowercase english letters and some queries. For each query (l,r,k), please output the s...

dp

2019-08-27

0 536

后缀数组模板

#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; const int inf = 1e9; struct SA { int dp[maxn][20], sa[maxn], rak[m...

2019-08-25

0 576

CF126B(后缀数组求LCP + 扩展KMP求LCP）

Asterix，Obelix和他们的临时伙伴Suffix、Prefix已经最终找到了和谐寺。然而和谐寺大门紧闭，就连Obelix的运气也没好到能打开它。不久他们发现了一个字符串S（|S|<=1000000），刻在和谐寺大门下面的岩石上。Asterix猜想那一定是打开寺庙大门的密码，于是就大声...

2019-07-31

0 773

51nod 1292 字符串中的最大值 V2 （后缀数组）

有一个字符串T。字符串S的F函数值可以如下计算：F(S) = L * S在T中出现的次数（L为字符串S的长度）。求所有T的子串S中，函数F(S)的最大值。输入输入字符串T, (1 <= L <= 1000000， L为T的长度)，T中的所有字符均为小写英文字母。输出输出T的所有子...

2019-05-04

0 450

51nod 1277 字符串中的最大值 (后缀数组求height[i]）

一个字符串的前缀是指包含该字符第一个字母的连续子串，例如：abcd的所有前缀为a, ab, abc, abcd。给出一个字符串S，求其所有前缀中，字符长度与出现次数的乘积的最大值。例如：S = “abababa” 所有的前缀如下: “a”, 长度与出现次数的乘积 1 * 4 = 4, “ab”...

2019-05-04

0 489

1304 字符串的相似度后缀数组

我们定义2个字符串的相似度等于两个串的相同前缀的长度。例如 “abc” 同 “abd” 的相似度为2，“aaa” 同 “aaab” 的相似度为3。给出一个字符串S，计算S同他所有后缀的相似度之和。例如：S = “ababaa”，所有后缀为： ababaa 6 babaa 0 abaa 3 baa...

2019-04-29

0 441

1304 字符串的相似度后缀数组

我们定义2个字符串的相似度等于两个串的相同前缀的长度。例如 “abc” 同 “abd” 的相似度为2，“aaa” 同 “aaab” 的相似度为3。给出一个字符串S，计算S同他所有后缀的相似度之和。例如：S = “ababaa”，所有后缀为： ababaa 6 babaa 0 abaa 3 baa...

2019-04-29

0 427

Suffix

Consider n given non-empty strings denoted by s1 , s2 , · · · , sn . Now for each of them, you need to select a corresponding suffix, denoted by suf1,...

2019-04-28

0 466

hihCoder 后缀数组四·重复旋律4

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分。我们把一段旋律称为(k,l)-重复的，如果它满足由一个长度为l的字符串重复了k次组成。如旋律abaabaabaaba是(4,3)重复的，因为...

2019-04-28

0 457

1732 51nod婚姻介绍所后缀数组

51nod除了在做OJ之外，还开展了很多副业。婚姻介绍所就是其中之一。对于一个客户，我们可以使用一个字符串来描述该客户的特质。假设现在我们有两个客户A和B。 A的特质字符串为：abcdefg B的特质字符串为：abcxyz 则A和B的匹配度f(A, B)为A和B的最长公共前缀的长度，即l...

2019-04-26

0 432