poj 3261 Milk Patterns (最长公共子串,后缀数组)

poj3261

题意:给一个字符串,要求找出至少出现k次的最长重复子串…

思路:后缀数组,然后再次用到了根据height数组对后缀进行分组的套路…二分判定合法性,对于当前的最长长度x,分组使得每组中的height[i]都大于等于x,所不同的是,判定变成了存在一个组,后缀的个数至少[……]

Read more

poj 1743 Musical Theme (不可重叠最长重复子串,后缀数组)

poj 1743

题意:n个数字(1..88)表示的音符,问最长的连续两段长度至少为5的变化相同的音符段的长度。。。

思路:求最长重复字串。。。。很容易想到后缀数组。。但是这道题多了一个不可重叠的要求。

先二分答案,把题目变成判定性问题:判断是否
存在两个长度为 k 的子串是相同的,[……]

Read more

ural 1517. Freedom of Choice (后缀数组,最长公共子串)

ural1517
题意:给出两个字符串,求最长的公共字串(要求出具体的字符串是什么)

思路:依然是后缀数组,在更新长度 的时候记录起始位置即可,1A。以及,发现多开了一个完全没有必要的数组w[],这次已删。

 

20160730update:模板已更正,lrj的模板的r[……]

Read more

poj 2774 Long Long Message (最长公共字串,后缀数组模板题)

poj2774

题意:给出两个字符串,问最长的公共连续字串。

思路:后缀数组模板题。

具体可以参考两篇国集论文(09,04)
topcoder中的讲解
codechef上的讲解
还有一篇讲 dc3算法的论文:SuffixArrays_dc3
这里不谈具体的后缀数组的学习内容[……]

Read more