最长重复子串

2024年8月28日 | 阅读 7 分钟

“最长重复子串”问题是计算机科学中一个众所周知的挑战，用于确定给定字符串中出现两次或两次以上的长度最长的子串。也就是说，我们必须找到在原始字符串中最多出现两次的子串。

示例

输入字符串: "AABABCA" 最长重复子序列: "ABA"

输入字符串: "ABCDABC" 最长重复子序列: "ABC"

输入字符串: "Mississippi" 最长重复子序列: "issi"

如何找到最长重复子序列

朴素方法

算法

生成给定字符串的所有可能子串。
创建一个字符串的后缀数组。
对后缀数组进行排序。
比较相邻后缀以找到共同前缀（即最长公共子串）。
返回找到的最长公共子串。

示例 1

字符串 = "banana"

步骤 1： 为给定字符串 "banana" 生成所有可能的子串。

以下是单词 "banana" 的子串

"b", "ba", "ban", "bana", "banan", "a", "an", "ana", "anan", "n", "nan", "nana", "a", "an", "ana", "n", "na," "a."

步骤 2

将文本 "banana" 的后缀添加到数组中

后缀数组是一个字符串后缀起始索引的数组，按字典顺序排列。它将如下所示

后缀数组

[5, 3, 1, 0, 4, 2]

对应的后缀是：["a", "ana", "anana", "banana", "na", "nana"]。

步骤 3： 后缀数组排序

排序后后缀数组不变

排序后的后缀数组：[5, 3, 1, 0, 4, 2]

步骤 4： 比较相邻后缀以识别共同前缀（即最长公共子串）

现在通过比较排序后的后缀数组中相邻的后缀来发现最长公共前缀 (LCP)。两个后缀 SA[i] 和 SA[i+1] 之间的公共前缀的长度就是 LCP 值。

LCP 数组：[0, 1, 3, 0, 0]

它解释说，第一个后缀 ("ana") 和第二个后缀 ("anana") 的 LCP 长度为 1 ("a")，第二个后缀 ("anana") 和第三个后缀 ("banana") 的 LCP 长度为 3，所有其他对的 LCP 长度为 0（没有共同前缀）。

步骤 5： 找到最长公共子串并返回它

LCP 数组显示 "ana" 的最长公共子串长度为 3。

这意味着 "ana" 是字符串 "banana" 中最长的重复子串 (LRS)。

Java 代码

import java.util.Arrays;
public class LongestRepeatedSubstring 
{
    // Function to generate all possible substrings of a given string
    private static String[] generateSubstrings(String input) 
       {
        int n = input.length();
        String[] substrings = new String[n * (n + 1) / 2];
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) 
           {
                substrings[index++] = input.substring(i, j);
            }
        }
        return substrings;
    }

    // Function to create the suffix array of the given string
    private static int[] createSuffixArray(String input)
      {
        int n = input.length();
        Suffix[] suffixes = new Suffix[n];
        for (int i = 0; i < n; i++) {
            suffixes[i] = new Suffix(i, input.substring(i));
        }
        Arrays.sort(suffixes);
        int[] suffixArray = new int[n];
        for (int i = 0; i < n; i++) 
        {
            suffixArray[i] = suffixes[i].index;
        }
        return suffixArray;
    }

    // Class representing a suffix with its starting index and the suffix string
    private static class Suffix implements Comparable<Suffix> 
      {
        int index;
        String suffixString;

        Suffix(int index, String suffixString) {
            this.index = index;
            this.suffixString = suffixString;
        }

        @Override
        public int compareTo(Suffix other) 
        {
            return this.suffixString.compareTo(other.suffixString);
        }
    }

    // Function to find the Longest Repeated Substring
    private static String findLongestRepeatedSubstring(String input) 
     {
        // Step 1: Generate all possible substrings of the given string
        String[] substrings = generateSubstrings(input);

        // Step 2: Create a suffix array of the string
        int[] suffixArray = createSuffixArray(input);

        // Step 3: Compare adjacent suffixes to find common prefixes (i.e., longest common substrings)
        int n = input.length();
        int[] lcp = new int[n];
        for (int i = 1; i < n; i++) 
         {
            int j = suffixArray[i - 1];
            int k = suffixArray[i];
            int lcpLength = 0;
            while (j < n && k < n && input.charAt(j) == input.charAt(k)) {
                lcpLength++;
                j++;
                k++;
            }
            lcp[i] = lcpLength;
        }

        // Step 4: Find the longest common substring
        int maxLength = 0;
        int longestSuffixIndex = 0;
        for (int i = 1; i < n; i++) {
            if (lcp[i] > maxLength) {
                maxLength = lcp[i];
                longestSuffixIndex = i;
            }
        }

        // Step 5: Return the longest common substring found
        String longestRepeatedSubstring = substrings[suffixArray[longestSuffixIndex]].substring(0, maxLength);
        return longestRepeatedSubstring;
    }

    public static void main(String[] args) {
        String input = "banana";
        String lrs = findLongestRepeatedSubstring(input);
        System.out.println("Longest Repeated Substring: " + lrs);
    }
}

输出

Longest Repeated Substring: ana

为了确定给定字符串中的最长重复子串 (LRS)，提供的 Java 代码使用了一种算法。为此，它生成所有可能的子串，构建一个后缀数组，并计算最长公共前缀 (LCP) 数组以查找公共子串。然后，该算法返回发现的最长重复子串。使用 "banana" 作为输入的示例输出是 "ana"。通过使用排序后缀数组和 LCP 数组，该技术有效地以 O(n log n) 的时间复杂度解决了 LRS 问题，使其适用于大型字符串。

解决最长重复子串的有效方法

算法

创建给定字符串的后缀数组。
生成 LCP 数组，其中 LCP[i] 表示从位置 SA[i] 和 SA[i+1] 开始的后缀之间的最长公共前缀的长度。
遍历 LCP 数组以找到最大的 LCP 值和相应的后缀。
与最大 LCP 值对应的子串是最长重复子串。

示例

步骤 1： 从提供的字符串 "banana" 创建一个后缀数组

后缀数组是一个字符串后缀起始索引的数组，按字典顺序排列。

单词 "banana" 的后缀数组是 [5, 3, 1, 0, 4, 2]。

步骤 2： 生成 LCP 数组

LCP 数组被创建，其中存储了后缀数组中相邻后缀之间的最长公共前缀的长度。

字符串 "banana" 的 LCP 数组是 [0, 1, 3, 0, 0]。

步骤 3： 找到最长重复子串

遍历 LCP 数组后，我们发现最长重复子串的最大长度为 3，它存在于后缀 "ana" 和 "anana" 之间。

步骤 4： 返回最长重复子串："ana" 的长度为 3，是最长重复子串。

因此，字符串 "banana" 中最长的重复子串是 "ana"。

实施

在 Java 中

import java.util.Arrays;
public class LongestRepeatedSubstring 
{
    // Function to create the suffix array of the given string
    private static int[] createSuffixArray(String input) {
        int n = input.length();
        Suffix[] suffixes = new Suffix[n];
        for (int i = 0; i < n; i++) 
        {
            suffixes[i] = new Suffix(i, input.substring(i));
        }
        Arrays.sort(suffixes);
        int[] suffixArray = new int[n];
        for (int i = 0; i < n; i++)
        {
            suffixArray[i] = suffixes[i].index;
        }
        return suffixArray;
    }
    // Class representing a suffix with its starting index and the suffix string
    private static class Suffix implements Comparable<Suffix>
      {
        int index;
        String suffixString;

        Suffix(int index, String suffixString) 
        {
            this.index = index;
            this.suffixString = suffixString;
        }
        public int compareTo(Suffix other)
       {
            return this.suffixString.compareTo(other.suffixString);
        }
    }
    // Function to generate the LCP array
    private static int[] generateLCPArray(String input, int[] suffixArray)
    {
        int n = input.length();
        int[] lcp = new int[n];
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) 
      {
            rank[suffixArray[i]] = i;
        }
        int k = 0;
        for (int i = 0; i < n; i++) 
          {
            if (rank[i] == n - 1) {
                k = 0;
                continue;
            }
            int j = suffixArray[rank[i] + 1];
            while (i + k < n && j + k < n && input.charAt(i + k) ==
            input.charAt(j + k)) 
           {
                k++;
            }
            lcp[rank[i]] = k;
            if (k > 0) {
                k--;
            }
        }
        return lcp;
    }
    // Function to find the Longest Repeated Substring
    private static String findLongestRepeatedSubstring(String input) 
   {
        // Step 1: Create a suffix array of the string
        int[] suffixArray = createSuffixArray(input);

        // Step 2: Generate the LCP array
        int[] lcp = generateLCPArray(input, suffixArray);
        // Step 3: Find the Longest Repeated Substring
        int maxLength = 0;
        int longestSuffixIndex = 0;
        for (int i = 0; i < input.length() - 1; i++) {
            if (lcp[i] > maxLength) {
                maxLength = lcp[i];
                longestSuffixIndex = i;
            }
        }
        // Step 4: Return the Longest Repeated Substring found
        String longestRepeatedSubstring = input.substring(suffixArray[longestSuffixIndex], suffixArray[longestSuffixIndex] + maxLength);
        return longestRepeatedSubstring;
    }
    public static void main(String[] args) 
{
        String input = "banana";
        String lrs = findLongestRepeatedSubstring(input);
        System.out.println("Longest Repeated Substring: " + lrs);
    }
}

输出

Longest Repeated Substring: ana

Java 代码使用后缀数组和 LCP 数组方法来定位最长重复子串。generateLCPArray 方法计算输入字符串的 LCP 数组，而 createSuffixArray 函数创建后缀数组。通过遍历 LCP 数组并查找相邻后缀之间的最长公共前缀来找到最长重复子串。输入 "banana" 的结果是 "ana"。该方法适用于具有重复子串的大型字符串，因为它以 O(n log n) 的时间复杂度有效地解决了问题，其中 n 是输入文本的长度。

下一个主题子串检查

最长重复子串

如何找到最长重复子序列

朴素方法

示例 1

解决最长重复子串的有效方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

最长重复子串

如何找到最长重复子序列

朴素方法

示例 1

解决最长重复子串的有效方法

相关帖子

如何检查给定数组是否代表堆

青蛙呱呱叫的最小数量

双指针技术

二叉树的右视图

数据结构中树的性质

生成两个数组的最大数

回文树

查找二叉搜索树中的第 k 小元素

查找二叉搜索树中两个节点之间的距离

螺旋形式打印给定矩阵

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器