当前位置: 首页 > 知识库问答 >
问题:

寻找最长的重复子串

帅博远
2023-03-14

解决此问题的最佳方法(性能方面)是什么?有人建议我使用后缀树。这是最好的方法吗?

共有3个答案

符懿轩
2023-03-14

下面是一个使用最简单的后缀树实现最长重复子串的简单方法。后缀树通过这种方式非常容易实现。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

class Node
{
public:
    char ch;
    unordered_map<char, Node*> children;
    vector<int> indexes; //store the indexes of the substring from where it starts
    Node(char c):ch(c){}
};

int maxLen = 0;
string maxStr = "";

void insertInSuffixTree(Node* root, string str, int index, string originalSuffix, int level=0)
{
    root->indexes.push_back(index);

    // it is repeated and length is greater than maxLen
    // then store the substring
    if(root->indexes.size() > 1 && maxLen < level)
    {
        maxLen = level;
        maxStr = originalSuffix.substr(0, level);
    }

    if(str.empty()) return;

    Node* child;
    if(root->children.count(str[0]) == 0) {
        child = new Node(str[0]);
        root->children[str[0]] = child;
    } else {
        child = root->children[str[0]];
    }

    insertInSuffixTree(child, str.substr(1), index, originalSuffix, level+1);
}

int main()
{
    string str = "banana"; //"abcabcaacb"; //"banana";  //"mississippi";
    Node* root = new  Node('@');

    //insert all substring in suffix tree
    for(int i=0; i<str.size(); i++){
        string s = str.substr(i);
        insertInSuffixTree(root, s, i, s);
    }

    cout << maxLen << "->" << maxStr << endl;

    return 1;
}

/*
s = "mississippi", return "issi"
s = "banana", return "ana"
s = "abcabcaacb", return "abca"
s = "aababa", return "aba"
*/
齐雅畅
2023-03-14

看看http://en.wikipedia.org/wiki/Suffix_array——它们非常节省空间,并且有一些合理的可编程算法来生成它们,例如卡尔凯宁和桑德斯的“简单线性工作后缀阵列构造”

东方镜
2023-03-14

查看此链接:http://introcs.cs.princeton.edu/java/42sort/LRS.java.html

/*************************************************************************
 *  Compilation:  javac LRS.java
 *  Execution:    java LRS < file.txt
 *  Dependencies: StdIn.java
 *  
 *  Reads a text corpus from stdin, replaces all consecutive blocks of
 *  whitespace with a single space, and then computes the longest
 *  repeated substring in that corpus. Suffix sorts the corpus using
 *  the system sort, then finds the longest repeated substring among 
 *  consecutive suffixes in the sorted order.
 * 
 *  % java LRS < mobydick.txt
 *  ',- Such a funny, sporty, gamy, jesty, joky, hoky-poky lad, is the Ocean, oh! Th'
 * 
 *  % java LRS 
 *  aaaaaaaaa
 *  'aaaaaaaa'
 *
 *  % java LRS
 *  abcdefg
 *  ''
 *
 *************************************************************************/


import java.util.Arrays;

public class LRS {

    // return the longest common prefix of s and t
    public static String lcp(String s, String t) {
        int n = Math.min(s.length(), t.length());
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != t.charAt(i))
                return s.substring(0, i);
        }
        return s.substring(0, n);
    }


    // return the longest repeated string in s
    public static String lrs(String s) {

        // form the N suffixes
        int N  = s.length();
        String[] suffixes = new String[N];
        for (int i = 0; i < N; i++) {
            suffixes[i] = s.substring(i, N);
        }

        // sort them
        Arrays.sort(suffixes);

        // find longest repeated substring by comparing adjacent sorted suffixes
        String lrs = "";
        for (int i = 0; i < N - 1; i++) {
            String x = lcp(suffixes[i], suffixes[i+1]);
            if (x.length() > lrs.length())
                lrs = x;
        }
        return lrs;
    }



    // read in text, replacing all consecutive whitespace with a single space
    // then compute longest repeated substring
    public static void main(String[] args) {
        String s = StdIn.readAll();
        s = s.replaceAll("\\s+", " ");
        StdOut.println("'" + lrs(s) + "'");
    }
}
 类似资料:
  • 具有任意字符串的,如 我是否可以找到由空格分隔的重复子字符串(编辑)?在这种情况下,它将是“你好”、“我是”和“字符串”。 我一直在想这个问题有一段时间了,但我仍然找不到任何真正的解决办法。我也读过一些关于这个主题的文章,并偶然发现了后缀树,但即使我需要找到每一个重复,例如重复数大于2,这能帮助我吗? 如果是这样,是否有一些python库可以处理后缀树并对其执行操作? 编辑:很抱歉我说得不够清楚。

  • 我正在寻找一种快速算法,搜索给定字符串中最长的重复子字符串(至少重复1次),并尽可能降低时间复杂度和(如果可能)内存(RAM)。 我见过一些实现,但大多数都不是为大量字符设计的(比如说)。一个例子是: 我已经尝试了100次包含的字符串。 它适用于小弦( 编辑:有没有办法不用在内存中加载一个(比如20GB)文件就可以做到这一点?

  • 给定一个数组< code>a[0..< code>0之间的整数的N-1] 例: 输入 预期输出:

  • 可能重复: 查找字符串中最长的重复序列 我正在解决一个问题,我需要找到重复最多的模式。 为了简单和方便,请考虑这个字符串: 重复次数最多的序列(例如,最初考虑字符串长度大于3个字符)是“Lorem Ipsum”。“Lorem”和“Ipsum”当然也重复相同的次数,但如果它们重复相同的次数,则较长的字符串优先于较短的字符串。 什么样的算法可以有效地找到这种模式,最好是在Python中?

  • 本文向大家介绍Python实现针对给定字符串寻找最长非重复子串的方法,包括了Python实现针对给定字符串寻找最长非重复子串的方法的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python实现针对给定字符串寻找最长非重复子串的方法。分享给大家供大家参考,具体如下: 问题: 给定一个字符串,寻找其中最长的重复子序列,如果字符串是单个字符组成的话如“aaaaaaaaaaaaa”那么满足要求的

  • 我知道这是一个有点老生常谈的话题,但我已经达到了从已经得到的答案中得到的帮助的极限。 这是针对Rosalind项目问题LREP的。我试图找到字符串中最长的k-peated子串,我得到了后缀树,这很好。我知道我需要用每个节点的后代叶子数来注释后缀表,然后用