精华内容
下载资源
问答
  • 最长重复子串

    2021-03-08 09:44:06
    一、问题描述给定一个字符串,求出其最长重复子串例如:abcdabcd ,最长重复子串是 abcd最长重复子串可以重叠例如:abcdabcda ,这时最长重复子串是 abcda ,中间的 a 是被重叠的。二、分析1、直观的解法首先检测...

    一、问题描述

    给定一个字符串,求出其最长重复子串

    例如:abcdabcd ,最长重复子串是 abcd

    最长重复子串可以重叠

    例如:abcdabcda ,这时最长重复子串是 abcda ,中间的 a 是被重叠的。

    二、分析

    1、直观的解法

    首先检测长度为 n - 1 的字符串情况,如果不存在重复则检测 n - 2, 一直递减下去,直到 1 。

    这种方法的时间复杂度是 O(N * N * N),其中包括三部分,长度纬度、根据长度检测的字符串数目、字符串检测。

    2、使用后缀数组

    后缀数组:例如对于字符串String str="banana"的后缀数组是a[0]="anana",a[1]="nana",a[2]="ana",a[3]="na",a[4]="a",

    改进的方法是利用后缀数组:对一个字符串生成相应的后缀数组后,然后再排序,排完序依次检测相邻的两个字符串的开头公共部分。

    这样的时间复杂度为:

    1)生成后缀数组 O(N)

    2)排序 O(NlogN*N) 最后面的 N 是因为字符串比较也是 O(N)

    3)依次检测相邻的两个字符串 O(N * N)

    总的时间复杂度是 O(N^2*logN)

    三、java实现

    分为三步:

    第一步:初始化后缀数组

    第二步:对后缀数组进行按字典排序

    第三步:对后缀数组中相邻元素进行比较,求最长子串

    public classMaxSameString {/** 比较两个相邻的字符串*/

    public intsameLen(String str1,String str2){int index=0;while(index

    index++;

    }else{break;

    }

    }returnindex;

    }/** 使用快速排序,对字符串按照字典顺序排列*/

    public void quickSort(String[] after,int start,intend){int low=start;int high=end;

    String pkey=after[low];while(low0) high--;

    after[low]=after[high];while(low

    after[high]=after[low];

    }

    after[low]=pkey;if(start

    quickSort(after, low+1, end);

    quickSort(after, start, low-1);

    }

    }/***@paramargs*/

    public static voidmain(String[] args) {//TODO Auto-generated method stub

    MaxSameString mss=newMaxSameString();

    String src="banana";//待处理数组

    String[] after=new String[src.length()-1];//后缀数组//第一步:初始化后缀数组

    for(int i=0;i

    after[i]=src.substring(i+1);

    }//第二步:对后缀数组进行按字典排序

    mss.quickSort(after, 0,after.length-1);int maxlen=0;int maxi=0;//最长字符串出现在后缀数组中的位置//第三步:对后缀数组中相邻元素进行比较,求最长子串

    for(int i=0;imaxlen){

    maxlen=tmp;

    maxi=i;

    }

    }

    System.out.println("Max length is "+maxlen);

    }

    }

    展开全文
  • 返回任何具有最长可能长度的重复子串。(如果 S不含重复子串,那么答案为""。) 示例 1: 输入:"banana" 输出:"ana" 示例 2: 输入:"abcd" 输出:"" 提示: 2 <= S.length <= 10^5 S 由小写英文...

    给出一个字符串 S,考虑其所有重复子串(S 的连续子串,出现两次或多次,可能会有重叠)。

    返回任何具有最长可能长度的重复子串。(如果 S 不含重复子串,那么答案为 ""。)

     

    示例 1:

    输入:"banana"
    输出:"ana"

     

    示例 2:

    输入:"abcd"
    输出:""
     

    提示:

    2 <= S.length <= 10^5
    S 由小写英文字母组成。


    解题思路:

    二分查找 + Rabin-Karp 字符串编码。

    我们可以把这个问题分解成两个子问题:

    1. 从 1 到 N 中选取子串的长度 L

    2. 检查字符串中是否存在长度为 L 的重复子串。

     

    Python代码:

    class Solution:
        def longestDupSubstring(self, s: str) -> str:
            def search(m, mod):
                h = 0
                for i in range(m):
                    h = (h * 26 + nums[i]) % mod
                al = pow(26, m, mod)
                seen = {h}
                for pos in range(1, n - m + 1):
                    h = (h * 26 - nums[pos - 1] * al + nums[pos + m - 1]) % mod
                    if h in seen:
                        return pos
                    seen.add(h)
                return -1
    
            n = len(s)
            nums = [ord(c) - ord('a') for c in s]
            l, r = 1, n
            mod = 2 ** 63 - 1
            pos = 0
            while l <= r:
                mid = (l + r) // 2
                cur = search(mid, mod)
                if cur != -1:
                    l = mid + 1
                    pos = cur
                else:
                    r = mid - 1
            return s[pos: pos+l-1]

     

    展开全文
  • 求串的最长重复子串长度(子串不重叠)。例如:abcaefabcabc的最长重复子串是串abca,长度为4。 输入 测试次数t t个测试串 输出 对每个测试串,输出最长重复子串长度,若没有重复子串,输出-1. 样例输入 3 ...

    题目描述

    求串的最长重复子串长度(子串不重叠)。例如:abcaefabcabc的最长重复子串是串abca,长度为4。

    输入

    测试次数t

    t个测试串

    输出

    对每个测试串,输出最长重复子串长度,若没有重复子串,输出-1.

    样例输入

    3
    abcaefabcabc
    szu0123szu
    szuabcefg

    样例输出

    4
    3
    -1

    展开全文
  • 我是新的java,我被赋予了分配以找到字符最长字符.我在网上研究,看来解决这个问题的好方法是实现后缀树.请告诉我如何做到这一点,或者如果您有任何其他解决方案.请记住,这是假设用低水平的java知识完成的....

    我是新的java,我被赋予了分配以找到字符串中最长的子字符串.

    我在网上研究,看来解决这个问题的好方法是实现后缀树.

    请告诉我如何做到这一点,或者如果您有任何其他解决方案.请记住,这是假设用低水平的java知识完成的.

    谢谢,谢谢.

    附:测试仪字符串让人放心.

    /**

    This method will find the longest substring of a given string.

    String given here is reassuring.

    */

    public String longestRepeatedSubstring()

    {

    String longestRepeatedSubstring = "";

    for (int i = 0; i

    {

    String one = text.substring(0,i);

    for(int o = 0; o

    {

    Sting two = text.substring(0,o);

    if(one.equals(two))

    {

    longestRepeatedSubstring = one;

    }

    }

    }

    return longestRepeatedSubstring;

    }

    解决方法:

    如果您调试代码,您将看到代码没有按照您的想法进行. AFAIK你需要至少三个循环,你不能假设你只会从第一个角色开始.这是一种可能的解决方案.

    public static void main(String[] args) throws IOException {

    String longest = longestDuplicate("ababcaabcabcaab");

    System.out.println(longest);

    }

    public static String longestDuplicate(String text) {

    String longest = "";

    for (int i = 0; i < text.length() - 2 * longest.length() * 2; i++) {

    OUTER:

    for (int j = longest.length() + 1; j * 2 < text.length() - i; j++) {

    String find = text.substring(i, i + j);

    for (int k = i + j; k <= text.length() - j; k++) {

    if (text.substring(k, k + j).equals(find)) {

    longest = find;

    continue OUTER;

    }

    }

    break;

    }

    }

    return longest;

    }

    版画

    abcaab

    为了“安慰”,它打印的不是我的第一个猜测.

    标签:java,string

    来源: https://codeday.me/bug/20191007/1865844.html

    展开全文
  • /*** 思路:"abdab" 拆分情况:1.ab abd abda abdab 2.bd bda bdab 3 da dab 4 ab 5 b** @param str* @return*/public static String find...// 最大字符String left;// 剩余字符int k = 0;// 计数器int len = ...
  • 假设我们有一个字符串,要如何求出在这个字符串里最长的重复子串呢?比如给出字符串abcdeefabcd,显然这个字符串的重复子串有很多,比如a、b、ab、abc 等等,那么通过观察,我们可以知道这个字符串的最长重复子串为...
  • NC142 最长重复子串 描述 定义重复字符串是由两个相同的字符串首尾拼接而成,例如 便是长度为6的一个重复字符串,而 则不存在重复字符串。 给定一个字符串,请返回其最长重复子串的长度。 若不存在任何重复字符子串...
  • 给定任意字符串,请帮小强找出其中的最长重复子串。 str1 = 'abcdiiabcdiierwyqu' # 设默认的最长重复字符串长度 print('str1:', str1, '长度为:', len(str1)) str1_start = 0 result = 0 for str1_max in ...
  • 返回任何具有最长可能长度的重复子串。(如果 S 不含重复子串,那么答案为 ""。) 数据范围: 2 <= S.length <= 10^5 S 由小写英文字母组成。 解法: 哈希预处理, 二分长度mid,用map存所有长度为mid的子串...
  • 最长重复子串 给出一个字符串 S,考虑其所有重复子串(S 的连续子串,出现两次或多次,可能会有重叠)。 返回任何具有最长可能长度的重复子串。(如果 S 不含重复子串,那么答案为 “”。) 示例 1: 输入:...
  • 需要java函数来查找字符最长重复子字符For instance, if the input is"banana",output should be"ana" and we have count the number of times it has appeared in this case it is 2.解决方法如下公开课...
  • 暴力破解–最长重复子串 文章目录暴力破解--最长重复子串本文知识点(你可能会学到):1. 求子串算法2.BF算法(串的模式匹配算法)3.求最长重复子串(遍历)完整代码end 本文知识点(你可能会学到): 求子串...
  • 后缀数组的应用:1、最长公共前缀 2、可重叠最长重复子串 3、不可重叠最长重复子串 4、可重叠的K次最长重复子串
  • 给定一个字符,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = “abcabcbb” 输出: 3 ...用left和right的位置当作最长重复子串的头和尾index; 用对象当作map使用, key ;字符,
  • 最长重复子串

    2021-06-27 21:07:28
    请勿修改,直接返回方法规定的值即可 * * @param a string字符 待计算字符 * @return int整型 */ int solve(string a) { // write code here if(a.size()) return 0; int len=a.size()/2; for(int i=len;i>=1;i-...
  • 以此找到最长重复子串 //在a[]数组中 以当前i下标开始 和 以k下标开始 开始游标比对(找到相同元素的时候调用,看它们之后的元素是否仍匹配) /* 在定长顺序存储结构表示串,求串中出现的第一个最长重复子串及其...
  • NC142 最长重复子串

    2021-09-15 18:10:58
    给定一个字符,请返回其最长重复子串的长度。 若不存在任何重复字符子串,则返回 0 。 数据范围: 字符长度不大于2 \times 10^42×104 示例1 输入: "ababc" 复制返回值: 4 复制说明: abab...
  • 最长重复子串 问题描述: 给定一个数组arr,返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。 示例1 输入:[2,3,4,5] 返回值:4 示例2 输入:[2,2,3,4,3] 返回值:3 备注: 1≤n≤10 ^5 直接暴力...
  • 1062. 最长重复子串 示例 1: 输入:“abcd” 输出:0 解释:没有重复子串。 示例 2: 输入:“abbaba” 输出:2 解释:最长的重复子串为 “ab” 和 “ba”,每个出现 2 次。 示例 3: 输入:“aabcaabdaab” ...
  • 方法一:二分查找+Rabin-Karp 字符编码 https://leetcode-cn.com/problems/longest-duplicate-substring/solution/zui-chang-zhong-fu-zi-chuan-by-leetcode/ class Solution: def longestDupSubstring
  • 1. 最长重复数组 (1)暴力 跟最长公共子串一个解法,没有变化 class Solution { public int findLength(int[] nums1, int[] nums2) { if (nums1 == null || nums2 == null) { return 0; } int l1 = nums1....
  • java 最长重复子串(中)

    2021-02-06 15:07:42
    重复字符看成是两个连续的窗口,窗口最大值为 len / 2,比较两个窗口内的字符,逐渐缩小窗口(O(n^3)) public int solve (String a) { // write code here char[] chars = a.toCharArray(); int len = ...
  • 二分查找+Robin-Karp算法 python class Solution: def longestDupSubstring(self, s: str): nums = [ord(c)-ord('a')+1 for c in s] n = len(nums) def check(L): P, Q = 131, 2**64 M = P**(L-1)%Q ...
  • D : DS串应用—最长重复子串 Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 38 Solved: 16 Description 求串的最长重复子串长度(子串不重叠)。例如:abcaefabcabc的最长重复子串是串abca,长度为4。 Input...
  • 参考链接: Python字符| digits 我尽量不在codeforces问题上寻求帮助,除非我真的,真的,卡住了,现在正好是。在Your first mission is to find the password of the Martian database. To achieve this, your ...
  • java public static String maxSameSubstring(String str) { String nstr = ""; if (str == null || str.length() == 0) return nstr; ArrayList<String> list = new ArrayList<...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,212
精华内容 17,684
关键字:

最长重复子串是什么