如何在不知道实际模式的情况下检查字符串中的重复模式？

Question

例如，我有一个字符串，“fbrtfuifigfbrt”。我想查找一个字符序列是否在字符串中重复出现，但我不知道该字符序列是什么。在本例中，它是 fbrt。

我考虑过将字符串分解成一堆单独的单词，然后检查这些单词是否相同，但是当解析较长的字符串时，这很快就会变得低效。

目前，我实现了上述想法，但肯定还有更好的想法。

String s = "fbrtfuifigfbrt";
ArrayList<String> words = new ArrayList<String>(s.length() * s.length());

for(int outerLoop = 0; outerLoop <= s.length(); outerLoop++){
    for(int nestedLoop = 0; nestedLoop <= s.length(); nestedLoop++){
        words.add(fileContents.substring(outerLoop, nestedLoop));
    }
}
//I could dump the ArrayList in a HashSet and check if they are the same size, 
//then find those elements, etc. 
//but that goes along with the above code, and I would prefer to use a more efficient method

Answer 1

您需要有两个迭代器，第一个指针是整个字符串的全局迭代器，第二个迭代器用作搜索指针。假设第一个迭代器指向示例中的 char "f" 。我们需要找到全局迭代器之后所有 "f" 的位置。对于在全局迭代器之后找到的每个 "f"，我们需要在全局迭代器和局部迭代器之后一个一个地比较字符（将此视为两个指针以相同的速度移动，直到它们指向不同的字符）。一旦本地迭代器到达字符串的末尾，您可以将全局迭代器向前移动一个字符（是的，如果您的字符串中有 n 个字符，您需要这样做 n 次）。

很抱歉，代码是用 C++ 编写的，但逻辑在 Java 中是相同的。

更新：还有另一种方法来执行任务。一种流行的解决方案是使用后缀树来存储文本。然后，您可以使用任何给定子字符串搜索后缀树，以查找给定子字符串在整个文本中的出现次数。树的构建是 O(n)，搜索子字符串取决于字母表的大小，如果您只使用英文字母，则为 26。所以如果你想找到所有重复出现的模式，你只需要对给定文本的每个子字符串执行搜索。这只会是 O(n^2)。所以这个算法比我提出的算法有整体优势。但如果你不需要性能，我的算法肯定能满足你的需要，因为它简单易行。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(int argc, const char * argv[]) {
    string s = "sdfssdddfssss";
    int pairCount = 0;
    vector<string> rep;
    for (int i = 0; i < s.length(); i++)
    {
        vector<int> idx;
        //find all index of all same char as s[i] after i
        //Note: You can optimize this by creating a map of index of 26 letters.
        for (int j = i+1; j < s.length(); j++)
            if (s[i] == s[j]) idx.push_back(j);
        int offset = 0;
        for (int j = 0; j < idx.size(); j++)
        {
            while (s[i+offset] == s[idx[j]+offset])
            {
                cout << "Pair found! " << s.substr(i, offset+1) << " " << i << " " << idx[j] << " " << offset + 1 << endl;
                pairCount++;
                offset++;
            }
            offset = 0;
        }
    }
    cout << "Pair count: " << pairCount;
    return 0;
}

Answer 2

这方面没有很好的优化。你最终会得到某种蛮力解决方案。

类似于：

String myString = "abcabcbbb";
//for each char
for (int i = 0; i < myString.length(); i++) {
    //for each substring starting with that char
    int maxSubStringLen = Math.floorDiv(myString.length() - i, 2);
    for (int j = 1; j <= maxSubStringLen; j++) {
        //get the substring
        String subString = myString.substring(i, i + j);
        int repetitionIndex = i + j;
        String repetition = myString.substring(repetitionIndex, repetitionIndex + subString.length());

        //does the substring repeat?
        if (subString.equals(repetition)) {
            System.out.println(subString);
        }
    }
}

这只是打印了 mach 的所有子字符串。您可以将 print 语句替换为您实际想要对它们执行的任何操作。

Answer 3

Java 中的工作解决方案：

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String test1 = "fbrtfuifigfbrt";
        String test2 = "abcdabcd";
        String test3 = "fbrtxibrjkfbrt";
        System.out.println(findRepetitions(test1));
        System.out.println(findRepetitions(test2));
        System.out.println(findRepetitions(test3));
    }

    private static List<String> findRepetitions(String string) {
        List<String> patternsList = new ArrayList<>();
        int length = string.length();
        for (int i = 0; i < length; i++) { // search the first half
            int limit = (length - i) / 2; // candidates can't be longer than half the remaining length
            for (int j = 1; j <= limit; j++) {
                int candidateEndIndex = i + j;
                String candidate = string.substring(i, candidateEndIndex);
                if (string.substring(candidateEndIndex).contains(candidate)) {
                    patternsList.add(candidate);
                }
            }
        }
        return patternsList;
    }
}

输出：

[f, fb, fbr, fbrt, b, br, brt, r, rt, t, f, i, f]
[a, ab, abc, abcd, b, bc, bcd, c, cd, d]
[f, fb, fbr, fbrt, b, br, brt, r, rt, t, b, br, r]

正如其他人所说，如果您不知道模式的长度或任何其他适用的限制，就没有简单的优化。

如果你想天真地丢弃像f、fb、fbr这样的子模式，因为它们是最长的 fbrt 模式，你可以使内部 for 向下计数，从 limit 向下计数到 1，这样你会先找到更长的模式，然后检查下一个模式是否是子串已经找到的，然后再将它们添加到列表中。像这样：

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String test1 = "fbrtfuifigfbrt";
        String test2 = "abcdabcd";
        String test3 = "fbrtxibrjkfbrt"; // "br" is a pattern but this version won't find it
        System.out.println(findRepetitions(test1));
        System.out.println(findRepetitions(test2));
        System.out.println(findRepetitions(test3));
    }

    private static List<String> findRepetitions(String string) {
        List<String> patternsList = new ArrayList<>();
        int length = string.length();
        for (int i = 0; i < length; i++) { // search the first half
            int limit = (length - i) / 2; // candidates can't be longer than half the remaining length
            for (int j = limit; j >= 1; j--) {
                int candidateEndIndex = i + j;
                String candidate = string.substring(i, candidateEndIndex);
                if (string.substring(candidateEndIndex).contains(candidate)) {
                    boolean notASubpattern = true;
                    for (String pattern : patternsList) {
                        if (pattern.contains(candidate)) {
                            notASubpattern = false;
                            break;
                        }
                    }
                    if (notASubpattern) {
                        patternsList.add(candidate);
                    }
                }
            }
        }
        return patternsList;
    }
}

然而，这会阻止您在 fbrtxzbrjkfbrt 中找到 br，如输出所示（并且对于具有许多不同模式的字符串，它也会使算法变慢):

[fbrt, i]
[abcd]
[fbrt]

因此 天真地 部分。当然，您可以包含更多内部循环，以确保在实际丢弃它们之前，在原始字符串中找不到 "on their own" 被丢弃的候选对象……等等。这取决于您希望搜索的详细程度成为。

如何在不知道实际模式的情况下检查字符串中的重复模式？

How can I check for a reoccurring pattern in a string without knowing the actual pattern?

java

string

string-parsing