资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/算法设计 - 寻找一个字符串的重复子串LRS

算法设计 - 寻找一个字符串的重复子串LRS

shleyZ / 2907人阅读

摘要：后缀数组最典型的是寻找一个字符串的重复子串字符串大小比较字符串大小比较是指字典顺序，也就是对于两个字符串。注意，在语言中，后缀数组记录的也就是数组中的元素是一个字符指针，指向的是一个子串的起始字符。

虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/
.. 拒绝伸手复制党

问题描述：

首先这是一个单字符串问题。子字符串 R 在字符串 L 中至少出现两次，则称 R 是 L 的重复子串。比如字符串abcdeabcd的LRS的长度是2，LRS是abcd

Longest Repeated Substring in GEEKSFORGEEKS is: GEEKS
Longest Repeated Substring in AAAAAAAAAA is: AAAAAAAAA
Longest Repeated Substring in ABCDEFG is: No repeated substring
Longest Repeated Substring in ABABABA is: ABABA
Longest Repeated Substring in ATCGATCGA is: ATCGA
Longest Repeated Substring in banana is: ana
Longest Repeated Substring in abcpqrabpqpq is: ab (pq is another LRS here)
一些定义：

后缀：后缀是指从某个位置i 开始到整个串末尾结束的一个特殊子串。字符串r 的从第i 个字符开始的后缀表示为Suffix(i)，也就是Suffix(i)=r[i..len(r)]。

后缀数组：后缀数组SA 是一个一维数组，它保存1..n 的某个排列SA[1]，SA[2]，...，SA[n]，并且保证Suffix(SA[i]) < Suffix(SA[i+1])，1≤i
也就是将S 的n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA 中。
后缀数组最典型的是寻找一个字符串的重复子串

字符串大小比较： 字符串大小比较是指“字典顺序”，也就是对于两个字符串u、v。
令i 从1 开始顺次比较u[i]和v[i]，如果u[i]=v[i]则令i 加1，否则若u[i]v[i]则认为u>v（也就是vlen(u)或者i>len(v)仍比较不出结果，那么若len(u)v。

方法1 ：

O(n^3) 直接子串和子串比较，查看所有字符串
比如 字符串 abcdabd, 先遍历第一个元素a,从第二个开始找，找到某个跟他一样的，开始游标k++,j++...然后记录相等子串长度；然后遍历第二个元素b开始...


public class LRS {
    private static int statLen(String X, int k, int j) {
        int cur_len = 0;

        while(k

方法2


使用后缀数组降低时间复杂度为O(n^2)

后缀数组的定义：一个字符数组，定义了一个字符串每个后缀子串的起始地址，如下图是banana这个字符串的后缀数组：





可以使用Treeset 保存后缀数组的String们..


算法的主要思想



利用后缀数组实现记录下来所有可能子串的起始地址，(用后缀数组的好处就是把所有起始位置相同的字符都放一起，就不用移动第二个指针 来找哪些字符与第一个指针指向的字符相同了 降低了一个n的维度的复杂度)


然后利用排序，把起始地址一致的字符放在一起：

这样就简化了暴力法当中通过移动j来控制下一个相同元素的过程，（也就是少了一层循环，同利用后缀数组的好处）因为相同的字符被放在了相邻的位置，对以后缀数组的元素开始的子串两两比较就知道了重复子串的长度。


For example



比如上面那个banana例子，对banana的一次循环遍历，得到后缀数组如上图所示.


然后对其排序，我们就得到了:






这时候，遍历后缀数组，每相邻的子串就按照（下第二个图comlen函数）的方法，计算两个子串的公共长度。注意，在C++语言中，后缀数组记录的（也就是数组中的元素）是一个字符指针，指向的是一个子串的起始字符。Java语言没有指针，实现起来可能比较麻烦，看到别人的一种实现方式是利用Treeset，直接记录所有后缀数组对应的子串，但是感觉空间开销太大。





复杂度分析：


第一次遍历原始数组，得到后缀数组的复杂度是O（n）, 对后缀数组的排序复杂度是O(nlogn)， 计算最长重复子串，遍历后缀数组O（n）,每两个相邻元素的比较O（n）, 所以复杂度是O(n)+O(nlogn)+O(n^2) = O(n^2), 比暴力法的O（n^3）复杂度小，其主要的原因就是利用后缀数组这个数据结构缓存了每一个子串的起始位置，通过排序，避免了暴力法中通过j来定位的又一层循环~
GPU云服务器 云服务器 字符串找子串算法 字符串去重复高效算法 寻找重复数字 c语言 最大公共子串算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64323.html

相关文章

  • 字符串处理文章outline

    摘要：遇到问题查查，看看，大神的讲解问问岛胖君下面是我最近整理出来的关于字符串的文章的怎么翻译汇集目录非常希望强化博客的功能，比如分类，置顶。 虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党 最近在看算法和语言，基本属于看知识 --> java实现 --> 整理blog 这个路线。 遇到问题查查st...

    Karuru 评论0 收藏0

  • JS算法题之leetcode(1~10)

    摘要：先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回，若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 JS算法题之leetcode(1~10) 前言 一直以来，前端开发的知识储备在数据结构以及算法层面是有所暂缺的，可能归根于我们的前端开发的业务性质，但是我认为任何的编程岗位都离不开数据结构以及算法。因此，我作为...

    SoapEye 评论0 收藏0

  • Leecode-3 Longest Substring Without Repeating Char

    摘要：题目解析题目含义很简单，即求出没有字符重复的子字符串的长度。例如很明显就是个由完全重复字符组成的字符串，所以它的答案长度为。所以综合来看该算法的效率为。 题目 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: abcabcbbO...

    luzhuqun 评论0 收藏0

  • 前端算法题 | 这道题效率最高的算法，你可能不知道？

    摘要：当循环到的时候，记录一下这个最后一次出现的位置在哪里。最后，这道算法题的出处来自里面有各种各样的实现方法，可以作为参考。觉得本文对你有帮助请分享给更多人关注妙味前端加星标，关注更多内容 showImg(https://segmentfault.com/img/bVbj5DR?w=900&h=383); 寻找最长的不含有重复字符的子串 可能看标题不会明白这个题到底什么意思，来看看下面的例...

    zgbgx 评论0 收藏0

  • 寻找最长不重复子串

    摘要：寻找最长不重复子串思路时间复杂度为遍历字符串，过程中将出现过的字符存入字典，为字符，为字符下标用保存遍历过程中找到的最大不重复子串的长度用保存最长子串的开始下标如果字符已经出现在字典中，更新的值如果字符不在字典中，更新的值代码本题以及其它 寻找最长不重复子串 Longest Substring Without Repeating Characters Given a string, ...

    afishhhhh 评论0 收藏0

发表评论

登陆后可评论

0条评论

shleyZ

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<