Cruiying
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)
归档
标签
去牛客网
登录
/
注册
Cruiying的博客
全部文章
/ 后缀数组
(共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
533
后缀数组模板
#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
574
CF126B(后缀数组求LCP + 扩展KMP求LCP)
Asterix,Obelix和他们的临时伙伴Suffix、Prefix已经最终找到了和谐寺。然而和谐寺大门紧闭,就连Obelix的运气也没好到能打开它。 不久他们发现了一个字符串S(|S|<=1000000),刻在和谐寺大门下面的岩石上。Asterix猜想那一定是打开寺庙大门的密码,于是就大声...
2019-07-31
0
771
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
464
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
首页
上一页
1
2
下一页
末页