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) 后缀数组(15) 字典树(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)

/ 注册

全部文章（共193篇）

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 465

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

CodeForces 427D Match & Catch 后缀数组

Police headquarter is monitoring signal on different frequency levels. They have got two suspiciously encoded strings s1 and s2 from two different fre...

2019-04-25

0 443

P4051 [JSOI2007]字符加密后缀数组

喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如‘JSOI07’，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大...

2019-04-25

0 440

P4051 [JSOI2007]字符加密后缀数组

喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如‘JSOI07’，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大...

2019-04-25

0 463

P2852 [USACO06DEC]牛奶模式Milk Patterns 后缀数组(poj3261)

题意: 找出现至少k次的子串的最大长度. 思路：据贪心策略,子串变长答案不会减小,所以可以看做是求k个后缀的LCP.因为要求LCP的最大值,而LCP(suffix(sa[i]),suffix(sa[j]))=min{height[k]}(i<j,k∈[i,j]),显然当这k个后缀在排名上连续的...

2019-04-25

0 433

POJ 2774 后缀数组

https://wenku.baidu.com/view/ed1be61e10a6f524ccbf85fd.html 题意：求两个串的最长公共子串思路：在求出height数组之后，再把sa数组区分出来，只要其中一个sa[i] (s[i -1])数组是属于第一串，s[i - 1] (s[i])属于第...

2019-04-24

0 450

CF547B Mike and Feet

Mike is the president of country What-The-Fatherland. There are n n bears living in this country besides Mike. All of them are standing in a line and ...

2019-04-22

0 488

CF547B Mike and Feet

Mike is the president of country What-The-Fatherland. There are n n bears living in this country besides Mike. All of them are standing in a line and ...

2019-04-22

0 394