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

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

一、一个字符串

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

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

智能推荐

while循环&CPU占用率高问题深入分析与解决方案_main函数使用while(1)循环cpu占用99-程序员宅基地

文章浏览阅读3.8k次，点赞9次，收藏28次。直接上一个工作中碰到的问题，另外一个系统开启多线程调用我这边的接口，然后我这边会开启多线程批量查询第三方接口并且返回给调用方。使用的是两三年前别人遗留下来的方法，放到线上后发现确实是可以正常取到结果，但是一旦调用，CPU占用就直接100%(部署环境是win server服务器)。因此查看了下相关的老代码并使用JProfiler查看发现是在某个while循环的时候有问题。具体项目代码就不贴了，类似于下面这段代码。while(flag) {//your code;}这里的flag._main函数使用while(1)循环cpu占用99

【无标题】jetbrains idea shift f6不生效_idea shift +f6快捷键不生效-程序员宅基地

文章浏览阅读347次。idea shift f6 快捷键无效_idea shift +f6快捷键不生效

node.js学习笔记之Node中的核心模块_node模块中有很多核心模块,以下不属于核心模块,使用时需下载的是-程序员宅基地

文章浏览阅读135次。Ecmacript 中没有DOM 和 BOM核心模块Node为JavaScript提供了很多服务器级别，这些API绝大多数都被包装到了一个具名和核心模块中了，例如文件操作的 fs 核心模块，http服务构建的http 模块 path 路径操作模块 os 操作系统信息模块// 用来获取机器信息的var os = require('os')// 用来操作路径的var path = require('path')// 获取当前机器的 CPU 信息console.log(os.cpus._node模块中有很多核心模块,以下不属于核心模块,使用时需下载的是

数学建模【SPSS 下载-安装、方差分析与回归分析的SPSS实现(软件概述、方差分析、回归分析)】_化工数学模型数据回归软件-程序员宅基地

文章浏览阅读10w+次，点赞435次，收藏3.4k次。SPSS 22 下载安装过程7.6 方差分析与回归分析的SPSS实现7.6.1 SPSS软件概述1 SPSS版本与安装2 SPSS界面3 SPSS特点4 SPSS数据7.6.2 SPSS与方差分析1 单因素方差分析2 双因素方差分析7.6.3 SPSS与回归分析SPSS回归分析过程牙膏价格问题的回归分析_化工数学模型数据回归软件

利用hutool实现邮件发送功能_hutool发送邮件-程序员宅基地

文章浏览阅读7.5k次。如何利用hutool工具包实现邮件发送功能呢？1、首先引入hutool依赖<dependency> <groupId>cn.hutool</groupId> <artifactId>hutool-all</artifactId> <version>5.7.19</version></dependency>2、编写邮件发送工具类package com.pc.c..._hutool发送邮件

docker安装elasticsearch，elasticsearch-head，kibana，ik分词器_docker安装kibana连接elasticsearch并且elasticsearch有密码-程序员宅基地

文章浏览阅读867次，点赞2次，收藏2次。docker安装elasticsearch，elasticsearch-head，kibana，ik分词器安装方式基本有两种，一种是pull的方式，一种是Dockerfile的方式，由于pull的方式pull下来后还需配置许多东西且不便于复用，个人比较喜欢使用Dockerfile的方式所有docker支持的镜像基本都在https://hub.docker.com/docker的官网上能找到合..._docker安装kibana连接elasticsearch并且elasticsearch有密码

随便推点

Python 攻克移动开发失败！_beeware-程序员宅基地

文章浏览阅读1.3w次，点赞57次，收藏92次。整理 | 郑丽媛出品 | CSDN（ID：CSDNnews）近年来，随着机器学习的兴起，有一门编程语言逐渐变得火热——Python。得益于其针对机器学习提供了大量开源框架和第三方模块，内置..._beeware

Swift4.0_Timer 的基本使用_swift timer 暂停-程序员宅基地

文章浏览阅读7.9k次。//// ViewController.swift// Day_10_Timer//// Created by dongqiangfei on 2018/10/15.// Copyright 2018年飞飞. All rights reserved.//import UIKitclass ViewController: UIViewController { ..._swift timer 暂停

元素三大等待-程序员宅基地

文章浏览阅读986次，点赞2次，收藏2次。1.硬性等待让当前线程暂停执行，应用场景：代码执行速度太快了，但是UI元素没有立马加载出来，造成两者不同步，这时候就可以让代码等待一下，再去执行找元素的动作线程休眠，强制等待 Thread.sleep(long mills)package com.example.demo;import org.junit.jupiter.api.Test;import org.openqa.selenium.By;import org.openqa.selenium.firefox.Firefox.._元素三大等待