博客首页 → 后缀数组

最新文章列表

求字符串最长的重复子串

题目： 给定一个字符串，求出其最长的重复子串（最长重复子串可以重叠）。 如字符串abcdabcabcd，其最长的重复子串为abcd； 如字符串abcdabcda，其最长的重复子串为abcda。 算法思想： 对字符串生成相应的后缀数组，再对其排序，排序后依次检测相邻两个字符串的公共前缀，时间复杂度为O(N^2*logN)。 程序如下： #include<iostream> usi ...
算法后缀数组冒泡排序快速排序 
EalayKing 评论(0) 有3558人浏览 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 & ...
后缀数组编程珠玑python 
daweibalong 评论(0) 有2015人浏览 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。 ...
后缀数组poj 3729Facer’s stringacm数据结构 
暴风雪 评论(0) 有1524人浏览 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 ...
最长公共子串后缀数组hdoj 1403acm数据结构 
暴风雪 评论(0) 有1202人浏览 2012-03-27 20:48

[后缀数组]hdoj 4080：Stammering Aliens

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

[后缀数组]hdoj 3518：Boring counting

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

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

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

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

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

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

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

[后缀数组]hdoj 4162：Shape Number

大致题意：   题中的图片可以无视， 给出一串数，经过变化后变为另一个串，变化的方式是num[i]=abs(num[i+1]-num[i])，求变化后串的最小表示。   大致思路：    这里用的是后缀数组，把当前串复制一遍接到这个串后面做的，shi慢shi慢的……Orz。马上去学学最小表示去。   #include<iostream> #include<cstdi ...
后缀数组hdoj 4162acm数据结构字符串 
暴风雪 评论(0) 有1316人浏览 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 ...
后缀数组poj 3581字符串acm数据结构 
暴风雪 评论(2) 有2312人浏览 2012-02-23 21:26

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

大致题意：     给出一个字符串，求出这个字符串中最长的回文串。如果有多个回文串的长度相等且都是最大，则输出最靠前的那个。   大致思路：     首先肯定是要把原字符的逆序串接到原字符串的后面。然后便是从0~~len扫描这个字符串，假设第i个位置是一个回文的中心，然后求出i个i对应位置的lca的最大值即可。每次枚举时要分奇偶两种情况考虑。      献上两组数据：qweRTYewq   ...
后缀数组RMQural 1297字符串acm 
暴风雪 评论(0) 有2186人浏览 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], ……中的某相邻的两个。所以 ...
后缀数组poj 3693字符串acm数据结构 
暴风雪 评论(0) 有4059人浏览 2012-02-18 23:55

[后缀数组]poj 3294：Life Forms

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

[后缀数组]poj 3261：Milk Patterns

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

[后缀数组]poj 1743：Musical Theme

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

[后缀数组]poj 1226：Substrings

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

最近博客热门TAG

Java(141744) C(73651) C++(68608) SQL(64571) C#(59609) XML(59133) HTML(59043) JavaScript(54919) .net(54785) Web(54514) 工作(54118) Linux(50905) Oracle(49875) 应用服务器(43289) Spring(40812) 编程(39454) Windows(39381) JSP(37542) MySQL(37267) 数据结构(36424)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics