本月博客排行
-
第1名
Xeden -
第2名
fantaxy025025 -
第3名
bosschen - paulwong
- johnsmith9th
年度博客排行
-
第1名
青否云后端云 -
第2名
宏天软件 -
第3名
gashero - gengyun12
- wy_19921005
- vipbooks
- e_e
- benladeng5225
- wallimn
- ranbuijj
- javashop
- jickcai
- fantaxy025025
- zw7534313
- qepwqnp
- robotmen
- 解宜然
- ssydxa219
- zysnba
- sam123456gz
- sichunli_030
- tanling8334
- arpenker
- gaojingsong
- xpenxpen
- kaizi1992
- wiseboyloves
- jh108020
- xyuma
- ganxueyun
- wangchen.ily
- xiangjie88
- Jameslyy
- luxurioust
- mengjichen
- lemonhandsome
- jbosscn
- nychen2000
- zxq_2017
- lzyfn123
- wjianwei666
- forestqqqq
- ajinn
- siemens800
- hanbaohong
- 狂盗一枝梅
- java-007
- zhanjia
- 喧嚣求静
- Xeden
最新文章列表
后缀数组的python模拟--编程珠玑 15.2
今天看了编程珠玑第15章字符串的前两节,对于后缀数组这玩意很感兴趣(以前学的太少了),对于15.2节的求给定文本输入的最长重复子串的问题,顺着作者的思路和其网站( http://netlib.bell-labs.com/cm/cs/pearls/index.html )上的代码,用c语言实现了一下,网站上代码如下:
#include <stdlib.h>
#include & ...
后缀数组 不重叠最长重复子串 POJ 1743
题意:有N个音符的序列来表示一首乐曲,每个音符都是1..88范围内的整数,现在要找一个重复的主题。“主题”是整个音符序列的一个子串,它需要满足如下条件:
1.长度至少为5个音符。 2.在乐曲中重复出现。(可能经过转调,“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值)
3.重复出现的同一主题不能有公共部分。
首先看到转调,这很重要,一个序列中的数加上同一 ...
后缀数组习题
原文:http://hi.baidu.com/lewutian/blog/item/4d098138d29c34f9b311c725.html
单独把它列出来是因为这个东西真的很神奇~~~
后缀数组经典思想:多串合并+二分答案+最优性--->可行性
例 1 :最长公共前缀
给定一个字符串,询问某两个后缀的最长公共前缀。 // 直接套用,ans=min( height[ i ...
[后缀数组]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。 ...
[后缀数组]hdoj 3518:Boring counting
大致题意: 给出一个字符串,求出所有不重叠出现次数大于等于两次的子串的数目。
大致思路: 后缀数组的好题,思想很妙也很难想到。大致过程就是先枚举子串的长度tmp,对于每一个height值大于等于tmp的区间内找到sa的最大值和最小值,看他们之间的距离是否小于tmp,是的话则ans++;
#include<iostream>
#include<cs ...
[后缀数组+RMQ]poj 3693:Maximum repetition substring
大致题意: 给出一个字符串,求出内部循环次数最多的子串。如果答案有多个,输出字典序最小的。
大致思路:
先穷举长度L,然后求长度为L 的子串最多能连续出现几次。首先连续出现1 次是肯定可以的,所以这里只考虑至少2 次的情况。假设在原字符串中连续出现2 次,记这个子字符串为S,那么S 肯定包括了字符r[0], r[L], r[L*2],r[L*3], ……中的某相邻的两个。所以 ...
[后缀数组]poj 1226:Substrings
大致题意:
给出n个字符串,求出一个最长的串,使得这个串或者这个串的回文在所有n个字符串中都出现。
大致思路:
把每个字符串拆为两个串,分别是原字符串和原字符串的回文串,把他们连接起来,中间插入分隔符。再将每个这样的结构都连接起来,中间同样插入分隔符。再转化为二分+判定即可。要熟知height sa数组的定义。
#include<iostream> ...