梳理——后缀数组应用-程序员宅基地

// 难度从 * ~ ***** 递增，*为简单

一、一个字符串

1.POJ 1743——不可重叠的最长重复子串

题意：给一个字符串，求重复出现的子串中最长的，子串不能重叠。

难度：*

算法&&技巧：如果是求可以重叠直接找 Height 数组中最大的就可以，但是要不能重叠，就需要二分答案，并按照二分的结果把 Height 分组，判断存在的条件是某一组中 sa 的最大最小值相减大于二分长度。

2.POJ 3261——可重叠并且出现至少K次的最长子串

题意：给一个字符串，求在字符串中出现至少K次的子串，子串可以重叠。

难度：*

算法&&技巧：和上一题一样，二分然后分组，如果某组内的个数大于等于K个，return true。

3.SPOJ 694 & 705——子串个数

题意：给定一个字符串，求它不同的子串的个数。

难度：*

算法&&技巧：知道第 i 个后缀对子串个数的贡献是：n - sa[i] - h[i]，就可以了。

4.URAL1297——最长回文子串
题意：给定一个字符串，求最长的回文子串。
难度：**
算法&&技巧：关键是把字符串翻转，再将原串和翻转后的拼起来。然后在以每个字符为中心求最大的。就是找两个后缀的LCP，用RMQ预处理。

5.POJ2406——字符串的循环节
题意：给定一个字符串，求最短的循环节（也就是最长循环多少次）。
难度：*~**
算法&&技巧：和KMP的做法类似，枚举循环节长度K，看suffix(1)和suffix(K + 1)的LCP长度是否为n-K，是的话就是循环节，否则不是。因为suffix(1)固定，所以RMQ所有到suffix(1)的就行。

6.POJ3693——重复次数最多的连续重复子串
题意：给定一个字符串，求连续重复次数最多的子串。
难度：***
算法&&技巧：暴力枚举子串循环节长度L，那么重复子串一定包括s[0], s[L], s[L*2]...这些字符中的相邻两个，枚举这些字符，向前向后匹配，更新答案。其中向后匹配和上几题一样用RMQ求LCP就行，而向前我们暴力平移，只需要向前平移最多L-1个，因为再往前是L的倍数，上一层枚举的L*i会包括它。

小结：
单个字符串的问题还是比较简单的，通常离不开Height数组。常见的技巧有二分答案，将H数组分组。同时还有一些小模型：1、求不同子串个数：每个后缀的贡献是n - sa[i] - h[i]。2、重复子串 = 某两个后缀l,r的最长公共前缀 = min{H[R[l] ~ R[r]]}。可以用RMQ做到O(nlogn) 预处理，O(1)查询。

二、两个字符串

1.POJ 2774——最长公共子串

题意：给两个长度不超过 100000 的字符串，求他们的最长公共子串。
难度：*
算法&&技巧：字符串拼接，后缀数组，找 Height 数组中最大的（注意特判两个是否属于不同字符串）

2.POJ 3415——长度不小于K的公共子串个数
题意：给定两个字符串，求长度不小于K的公共子串的个数。
难度：***
算法&&技巧：字符串拼接，若属于a串的后缀p和属于b串的后缀q，它们的LCP长度因为L，则他们对答案的贡献为L-K+1。但是两两枚举复杂度太大。注意到之前小结提到的小模型2，LCP具有可以用单调栈维护。对于a的每个后缀找和它LCP大于等于K的b的后缀，统计答案，加入单调栈，此时如果最后加入的比原来的小，说明LCP更新了，减去之前变得不合法的就行了。对于b串再做一次即可。

小结：
感觉两个字符串的题目差不多都和公共的什么有关，比如公共子串，公共前缀什么的。有一个经典的做法：把两个字符串拼起来，中间用没出现过的字符相连。然后剩下的就和一个字符串的差不多了。

三、多个字符串

1.POJ 3294——出现在至少K个字符串中的最长子串
题意：给N个字符串，求出现在至少K个字符串中的最长子串。
难度：*
算法&&技巧：类似两个字符串的方法，把N个字符拼起来。后缀数组求H数组。二分答案对H数组分组，看每组中不同字符串的个数是否大于等于K。

2. SPOJ 220——出现每个字符串中至少两次且不重叠的最长子串
题意：给N个字符串，求出现每个字符串中至少两次且不重叠的最长子串。
难度：**
算法&&技巧：和上一道题相似，不同的是分组后看是不是在每个字符串中都出现，且两次出现的位置之差大于等于串的长度。

3.POJ 1226——出现或者翻转后出现在每个i字符串中的最长子串
题意：给N个字符串，求出现或者翻转后出现在每个字符串中的最长子串。
难度：**
算法&&技巧：和POJ 3294一样，只需要先将每个字符串翻转，并和原字符串拼起来，再把n个这样的字符串拼起来，之后的方法就完全一样了。

小结：
多个和两个的方法都基本一样，就是都拼起来，中间用没出现过的字符连接。但是因为有N个字符串，最后处理的时候应该都需要用二分，分组或者别的数据结构什么的维护，就是要降低时间复杂度，不然就成了O(n^2)了。

本文链接：https://blog.csdn.net/ALXPCUN/article/details/51232798

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

css选择器总结_加瓦class-程序员宅基地

文章浏览阅读287次。css选择器汇总，以及css选择器权重的讲解_加瓦class

MATLAB摄像头可以运行但是打不开视频_matlab使用摄像头成功但没图像-程序员宅基地

文章浏览阅读510次。今天在学习一个MATLAB关于摄像头操作的代码，运行之后摄像头会一闪一闪，但是就是打不开视频的画面，查看了半天代码发现代码也没有错，最后尝试着将代码中的下面这句中的320x240改为640x480就可以打开视频了vid = videoinput('winvideo', 1, 'YUY2_320x240'); 或者直接去掉第三个参数也可以，例如：vid = videoinput('w..._matlab使用摄像头成功但没图像

Zookeeper 命令和查看节点数据_zk集群如何查看znode大小-程序员宅基地

文章浏览阅读10w+次，点赞7次，收藏33次。1、ZooKeeper命令行在安装目录bin下，执行zkcli.cmd 或zkcli.sh。然后输入命令。常用命令：（1）查看数据：ls， ls2（2）获取数据：get2、四字命令一些数据使用zkCli命令查看不到，使用四字命令则可以获取到。（1）方式1，使用telnet命令可通过telnet或nc命令向ZooKeeper端口发送4个字符的命令。windows下..._zk集群如何查看znode大小

python爬虫网页解析之parsel模块_import parsel-程序员宅基地

文章浏览阅读1.7k次，点赞2次，收藏6次。python爬虫网页解析之parsel模块一.parsel模块安装官网链接https://pypi.org/project/parsel/1.0.2/pip install parsel==1.0.2二.模块作用改模块主要用来将请求后的字符串格式解析成re,xpath,css进行内容的匹配推荐Python大牛在线分享技术扣qun：855408893领域：web开发，爬虫，数据分..._import parsel

安卓国际化之strings.xml导入Excel表格及从excel恢复到Strings.xml中_安卓国际化 .string文件怎么打开-程序员宅基地

文章浏览阅读2k次，点赞5次，收藏12次。 APP国际化已经是一个比较常用的需求了，当然中文部分身为开发人员自己就能三两下搞定，如果是其他语种。。。emm，我们身为开发人员的是不会越俎代庖的（关键是懒其实是不会），还是交给专业人士好了，哈哈哈。如果你把整个strings.xml文件发给翻译人员，估计他们会一脸懵逼，叫他们直接把文件里面的中文翻译成英文，但是不能破坏xml里的尖括号的格式，让男翻译火冒三丈，让女翻译的男朋友偷偷发..._安卓国际化 .string文件怎么打开

Visual Studio 快捷键更改和设置_visual studio中提示内容的选中键怎么设置-程序员宅基地

文章浏览阅读9.1w次，点赞35次，收藏55次。Visual Studio 快捷键更改和设置Visual Studio是程序员最为经常利用的利器，一把利器没有快捷键的支持将会少了很多乐趣和便捷。Qt的快捷键也是非常灵活多变。一般来说Visual Studio中的有些快捷键将会让你大开眼界。举个简单例子，大家都知道Ctrl+C是复制功能，操作便是选中按键复制粘贴。但是你却忽略了：当光标在某一行代码上，你按ctrl+C键，将会复制一行，无需..._visual studio中提示内容的选中键怎么设置

随便推点

Linux下常用软件推荐列表（欢迎补充。。。）_linx软件-程序员宅基地

文章浏览阅读2.4k次。Linux下推荐的常用应用程序列表一,网页浏览1,firefoxfirefox是现在最火的一个浏览器,支持好多扩展和插件,也有很多漂亮的主题.firefox就是mozilla-firefox,他是把mozilla的网页浏览的功能分离为一个单独的浏览器.Firefox一般是linux系统自带的默认浏览器.2,opera(非开源免费软件)opera是号称最快的浏览器.能直接浏览wa_linx软件

华为20级技术官耗巨资3年整合出这份2700页网络协议精髓_tcp/ip协议族 pdf-程序员宅基地

文章浏览阅读145次。以上就是五份TCP/IP、网络协议、路由与交换机2700多页的学习笔记，相信看完这些，一定可以摸透它的。_tcp/ip协议族 pdf

计算机进制幼儿入门,少儿编程中，你该如何给孩子讲解进制问题-程序员宅基地

文章浏览阅读251次。今天继续来聊少儿编程，在聊这个话题之前，先来说一说昨天在上一篇文章中看到的评论，评论这样说，“你这么喜欢编程，有女朋友吗？”看到这条评论，我觉得非常有必要回复一下，这也是很多人对于编程人员的一个误会，总是认为编程人员那么忙碌，性格可能会有点古怪，甚至来说，是一个宅男，是一个不会讨女生欢迎的男生。但就我所知，就我的周边来是说，和我接触的一些做程序员的朋友，他们的收入都还算好，至少来说，在北上广深这些..._二进制怎么跟孩子将

Unity发布的WebGL页面应用实现全屏/非全屏切换_unity中web切换全屏-程序员宅基地

文章浏览阅读1.1k次。转载之https://blog.51cto.com/shuxiayeshou/2386140_unity中web切换全屏

自学JAVA第三天-巩固练习-java基础篇_从控制台接收2个考试的整数分数-程序员宅基地

文章浏览阅读1k次，点赞4次，收藏4次。业精于勤，荒于嬉；行成于思，毁于随。1. 第一题：考试平均分请编程，从控制台接收2个考试的整数分数：数学分数、英语分数。然后程序要计算并打印两科的平均分是多少？(结果取整数即可)import java.util.Scanner;public class average{ public static void main(Strang[] args){ //创建键盘接收对象 Scanner sc = new (System.in); System.out.print("请输入._从控制台接收2个考试的整数分数

C#中string型字段的区别（char、varchar、nchar、nvarchar）_string和nvarchar-程序员宅基地

文章浏览阅读7.5k次。源地址：http://www.cnblogs.com/mekong/archive/2009/04/17/1437996.html对于程序中的string型字段，SQLServer中有char、varchar、nchar、nvarchar四种类型来对应（暂时不考虑text和ntext），开建立数据库中，对这四种类型往往比较模糊，这里做一下对比。定长或变长所谓定长就是长度固定_string和nvarchar