最新文章列表

求字符串最长的重复子串

题目: 给定一个字符串,求出其最长的重复子串(最长重复子串可以重叠)。 如字符串abcdabcabcd,其最长的重复子串为abcd; 如字符串abcdabcda,其最长的重复子串为abcda。 算法思想: 对字符串生成相应的后缀数组,再对其排序,排序后依次检测相邻两个字符串的公共前缀,时间复杂度为O(N^2*logN)。 程序如下: #include<iostream> usi ...
EalayKing 评论(0) 有3605人浏览 2013-09-20 22:21

后缀数组的python模拟--编程珠玑 15.2

今天看了编程珠玑第15章字符串的前两节,对于后缀数组这玩意很感兴趣(以前学的太少了),对于15.2节的求给定文本输入的最长重复子串的问题,顺着作者的思路和其网站( http://netlib.bell-labs.com/cm/cs/pearls/index.html )上的代码,用c语言实现了一下,网站上代码如下: #include <stdlib.h> #include & ...
daweibalong 评论(0) 有2052人浏览 2012-08-24 10:11

后缀数组 不重叠最长重复子串 POJ 1743

题意:有N个音符的序列来表示一首乐曲,每个音符都是1..88范围内的整数,现在要找一个重复的主题。“主题”是整个音符序列的一个子串,它需要满足如下条件:     1.长度至少为5个音符。     2.在乐曲中重复出现。(可能经过转调,“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值)     3.重复出现的同一主题不能有公共部分。 首先看到转调,这很重要,一个序列中的数加上同一 ...
chulongya 评论(0) 有7人浏览 2012-08-20 14:49

后缀数组习题

原文:http://hi.baidu.com/lewutian/blog/item/4d098138d29c34f9b311c725.html 单独把它列出来是因为这个东西真的很神奇~~~ 后缀数组经典思想:多串合并+二分答案+最优性--->可行性 例 1 :最长公共前缀 给定一个字符串,询问某两个后缀的最长公共前缀。   // 直接套用,ans=min( height[ i ...
weirenhaojiu 评论(0) 有8人浏览 2012-08-19 20:14

后缀数组

原文:http://hi.baidu.com/lewutian/blog/item/4d098138d29c34f9b311c725.html 单独把它列出来是因为这个东西真的很神奇~~~ 后缀数组经典思想:多串合并+二分答案+最优性--->可行性 例 1 :最长公共前缀 给定一个字符串,询问某两个后缀的最长公共前缀。   // 直接套用,ans=min( height[ i ...
bibei1234 评论(0) 有12人浏览 2012-08-19 13:30

[后缀数组]poj 3729:Facer’s string

大致题意:     给出两个字符串a,b和一个数字k,求出a中存在多少后缀,使得其和b中所有后缀的lcp的最大值等于k。   大致思路:    又弱智了的说,上来就用后缀数组+RMQ来爆,O(n^2)的效率果断TLE了,不要bs我……在网上看到的正解是先求出a中存在多少后缀,使得其和b的所有后缀的lcp最大值大于等于k,再求出a中存在多少后缀,使得其和b的所有后缀的lcp最大值大于等于k+1。 ...
暴风雪 评论(0) 有1559人浏览 2012-03-28 17:11

[最长公共子串-后缀数组]hdoj 1403:Longest Common Substring

大致题意:    如题。   大致思路:    后缀数组+二分的简单应用,可以扩展到多串匹配中去   #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int nMax = 500000; int num[nMax]; i ...
暴风雪 评论(0) 有1239人浏览 2012-03-27 20:48

[后缀数组]hdoj 4080:Stammering Aliens

大致题意:     给出一个数字m和一个字符串str,求出str中至少出现m次的最长的子串长度,并且求出这些子串中最靠右的子串的位置。   大致思路:    先求出后缀数组,二分枚举这个长度mid,然后分析height数组的每个大于mid的区间。过程稍复杂,具体看我代码即可。   #include<iostream> #include<cstdio> #i ...
暴风雪 评论(0) 有1009人浏览 2012-03-27 12:54

[后缀数组]hdoj 3518:Boring counting

大致题意:    给出一个字符串,求出所有不重叠出现次数大于等于两次的子串的数目。   大致思路:    后缀数组的好题,思想很妙也很难想到。大致过程就是先枚举子串的长度tmp,对于每一个height值大于等于tmp的区间内找到sa的最大值和最小值,看他们之间的距离是否小于tmp,是的话则ans++;   #include<iostream> #include<cs ...
暴风雪 评论(0) 有1084人浏览 2012-03-26 17:07

[后缀数组]ural 1590:Bacon’s Cipher

大致题意:     给出一个字符串,求这个字符串有多少个不同的子串。   大致思路:     用后缀数组对这个字符串的所有后缀进行排序,然后依次根据每个后缀和排在他后面的那个后缀讨论即可。   #include<iostream> #include<cstdio> #include<cstring> using namespace std; ...
暴风雪 评论(0) 有1461人浏览 2012-03-18 17:32

[后缀数组]ural 1354:Palindrome. Again Palindrome

大致题意:    给出一个字符串,要求在这个字符串后面添加最少的字母使其成为回文串。   大致思路:    要注意添加的字母数不能为0,要分奇偶讨论。   #include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace s ...
暴风雪 评论(0) 有1043人浏览 2012-03-11 19:24

[后缀数组+RMQ]hdoj 1867:A + B for you again

大致题意:     给出两个字符串s1,s2。现在我们可以把s1接到s2后面或者把s2接到s1后面,拼接的方式是:如果前面字符的后缀中和后面字符串的前缀中存在相同的部分,我们便把这一部分从第一个字符串中去掉,并把后面的字符串接上去。现在求拼接后长度最小并且字典序最小的字符串。   大致思路:    把两个字符串拼在一起,中间插入分隔符。对这个串求出后缀数组,并根据后缀数组求出s1+s2生成的字 ...
暴风雪 评论(0) 有1444人浏览 2012-03-05 21:24

[后缀数组]hdoj 4162:Shape Number

大致题意:   题中的图片可以无视, 给出一串数,经过变化后变为另一个串,变化的方式是num[i]=abs(num[i+1]-num[i]),求变化后串的最小表示。   大致思路:    这里用的是后缀数组,把当前串复制一遍接到这个串后面做的,shi慢shi慢的……Orz。马上去学学最小表示去。   #include<iostream> #include<cstdi ...
暴风雪 评论(0) 有1355人浏览 2012-03-04 10:13

[后缀数组]poj 3581:Sequence

大致题意:     给出n个数,把这个数列分为三段,再把三段反转后连接在一起成为一个新串,求字典序最小的新串。   大致思路:     由于需要翻转,所以在输入时就按照反序输入。比如样例输入是5     10 1 2 3 4。我们从后向前读入就变为5     4 3 2 1 10。对这列数求出后缀数组。在大于2的后最中找到最小的后缀并输出。对于剩下的前缀s,我们把s串接到自己后面,也就是ss ...
暴风雪 评论(2) 有2375人浏览 2012-02-23 21:26

[后缀数组+RMQ]ural 1297:Palindrome

大致题意:     给出一个字符串,求出这个字符串中最长的回文串。如果有多个回文串的长度相等且都是最大,则输出最靠前的那个。   大致思路:     首先肯定是要把原字符的逆序串接到原字符串的后面。然后便是从0~~len扫描这个字符串,假设第i个位置是一个回文的中心,然后求出i个i对应位置的lca的最大值即可。每次枚举时要分奇偶两种情况考虑。      献上两组数据:qweRTYewq   ...
暴风雪 评论(0) 有2224人浏览 2012-02-22 19:10

[后缀数组+RMQ]poj 3693:Maximum repetition substring

大致题意:    给出一个字符串,求出内部循环次数最多的子串。如果答案有多个,输出字典序最小的。   大致思路:     先穷举长度L,然后求长度为L 的子串最多能连续出现几次。首先连续出现1 次是肯定可以的,所以这里只考虑至少2 次的情况。假设在原字符串中连续出现2 次,记这个子字符串为S,那么S 肯定包括了字符r[0], r[L], r[L*2],r[L*3], ……中的某相邻的两个。所以 ...
暴风雪 评论(0) 有4091人浏览 2012-02-18 23:55

[后缀数组]poj 3294:Life Forms

大致题意:    给出n个字符串。求出至少出现在n/2+1个字符串中的子串中,所有长度最大的子串。   大致思路:    二分+判定。输出的时候要加一个isp判定符,防止输出相同的字符串。   #include<iostream> #include<cstdio> #include<cstring> using namespace std; ...
暴风雪 评论(0) 有1331人浏览 2012-02-15 18:00

[后缀数组]poj 3261:Milk Patterns

大致题意:    给出一个长度为n的字符串,再给出一个数字k。求出现至少k次的子串中长度最大是多少,注:可覆盖。   大致思路:     后缀数组+二分判定……水水。   #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int ...
暴风雪 评论(0) 有1407人浏览 2012-02-15 17:39

[后缀数组]poj 1743:Musical Theme

大致题意:    给出n个数字。首先将这n个数前后做差,得到另一个长度是n-1的序列。求出这个序列的最长重复子串,且这些子串不能重叠。   大致思路:     还是后缀数组+二分判定。传说中楼爷的男人八题Orz   #include<iostream> #include<cstdio> #include<cstring> using name ...
暴风雪 评论(0) 有4159人浏览 2012-02-15 16:50

[后缀数组]poj 1226:Substrings

大致题意:     给出n个字符串,求出一个最长的串,使得这个串或者这个串的回文在所有n个字符串中都出现。   大致思路:     把每个字符串拆为两个串,分别是原字符串和原字符串的回文串,把他们连接起来,中间插入分隔符。再将每个这样的结构都连接起来,中间同样插入分隔符。再转化为二分+判定即可。要熟知height sa数组的定义。   #include<iostream> ...
暴风雪 评论(0) 有2949人浏览 2012-02-15 16:37

最近博客热门TAG

Java(141747) C(73651) C++(68608) SQL(64571) C#(59609) XML(59133) HTML(59043) JavaScript(54918) .net(54785) Web(54513) 工作(54116) Linux(50906) Oracle(49876) 应用服务器(43288) Spring(40812) 编程(39454) Windows(39381) JSP(37542) MySQL(37268) 数据结构(36423)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics