如何检查字符串是否有重复模式？

Question

我最近在一个面试问题中被问到这个问题：给定一个输入字符串，检查它是否具有重复模式并返回真或假。例如： "abbaabbaabbaabba"是一个重复的模式"abba"private boolean checkPattern(String input) { }我们如何使用正则表达式和不使用正则表达式来解决它？我对使用正则表达式和不使用正则表达式的方法都感兴趣。

Answer 1

对于它的价值，我找到了一个使用正则表达式的解决方案。

诀窍是在非空的第一组上使用反向引用。

^(.+)(?:\1)+$

正如@PatrickParker 指出的那样，如果您需要最小的重复模式，那么您可以使用惰性限定符

^(.+?)(?:\1)+$

Answer 2

如果没有正则表达式，您将不得不遍历每个可能的子字符串，该子字符串的长度可以被原始字符串的长度整除，从索引 0 开始，在原始字符串中并检查它是否重复。要检查它是否重复，您只需检查pattern.length()字符串中的每个字符数，看看它是否是模式。例如，它看起来像这样，

public boolean checkPattern(String str) {

    String pattern = "";

    for (int i = 0; i < str.length()/2; i++) {

        pattern += str.charAt(i);

        if (str.length() % pattern.length() == 0 && isRepeating(str, pattern)) {

            return true;

        }

    }

    return false;

}

public boolean isRepeating(String str, String pattern) {

    String leftover = str;

    int currIndex = leftover.indexOf(pattern);

    while (currIndex == 0) {

        if(currIndex + pattern.length() == leftover.length()) {

            return true; // you have reached the last possible instance of the pattern at this point

        }

        leftover = leftover.substring(currIndex + pattern.length());

        currIndex = leftover.indexOf(pattern);

    }

    return false;

}

就像用户 thebjorn 提到的那样，您可以通过仅在字符串的长度可被模式的长度整除时调用它来防止不必要的调用isRepeating，因此在 if 语句中进行模数检查。此外，模式可以在字符串中重复的最大长度是str.length()/2.

Answer 3

我意识到这篇文章有点过时了，但它出现在关于这个主题的谷歌搜索的顶部，并且由于没有一个答案提供我需要的东西，我最终制作了一个方法，我只是想添加它这篇文章供未来的搜索者使用。

此方法生成找到的一个或多个模式以及每个模式在原始字符串中重复的次数。

当我使用 string.matches() 尝试 @flakes 正则表达式时，只有当模式并排时它才匹配 true。所以它会匹配 101101 但不匹配 101234101 （它似乎不知道模式 101 在那里两次。

因此，如果您只需要知道您的字符串是否并排具有相同的模式，请使用以下代码：

if (myString.matches("^(.+?)(?:\\1)+$")) {

  //doSomethingHere

}

考虑到构建一个模式子串的想法，我想出了这个方法，它基本上构建了一个所有可能模式的列表。然后它遍历该列表并检查原始字符串以查看该模式是否在其中。显然，它将忽略比较中的第一次命中，因为模式将始终在源字符串中命中一次……由于模式是从源字符串创建的。

这是代码，显然您可以根据需要对其进行按摩：

private void checkForPattern(String userString) {

    String               buildString;

    LinkedList<String>   patterns    = new LinkedList<>();

    int                  size        = userString.length();

    int                  hits;

    int                  newSize;

    String[]             coreString  = new String[size];

    Map<String, Integer> hitCountMap = new HashMap<>();

    for (int x = 0; x < size; x++) {

        coreString[x] = userString.substring(x, x + 1);

    }

    for (int index = 0; index < size - 1; index++) {

        buildString = coreString[index];

        for (int x = index + 1; x < size; x++) {

            buildString = buildString + coreString[x];

            patterns.add(buildString);

        }

    }

    for (String pattern : patterns) {

        String check = userString.replaceFirst(pattern, "");

        if (check.contains(pattern)) {

            newSize = userString.replaceAll(pattern, "").length();

            hits    = (size - newSize) / pattern.length();

            hitCountMap.put(pattern, hits);

        }

    }

    for (String pattern : hitCountMap.keySet()) {

        System.out.println("Pattern: " + pattern +

                           " repeated " + hitCountMap.get(pattern) +

                           " times.");

    }

}

Answer 4

我不知道 RegEx，所以我会以不同的方式来做。这仅适用于字符串不是部分重复的字符串，即“xbcabbaabbaabbaxx”

首先，您获取输入字符串，并找到字符串大小的因素。素数意味着没有重复模式，因为重复模式意味着模式字符串长度的至少 2 的倍数。

感谢 Tot Zam：寻找给定整数的因数

public ArrayList<Integer> findFactors(int num) {        

    ArrayList<Integer> factors = new ArrayList<Integer>();

    // Skip two if the number is odd

    int incrementer = num % 2 == 0 ? 1 : 2;

    for (int i = 1; i <= Math.sqrt(num); i += incrementer) {

        // If there is no remainder, then the number is a factor.

        if (num % i == 0) {

            factors.add(i);

            // Skip duplicates

            if (i != num / i) {

                factors.add(num / i);

            }

        }

    }

    // Sort the list of factors

    Collections.sort(factors);

    return factors;

}

一旦你找到了数字的因子，在你的例子中是 16（结果是 1,2,4,8,16），并且不包括最大的因子（它本身），你现在可以创建一个循环并迭代细绳。您检查每个值与之前的值，并检查直到您使用 continue 获得正确的值

例如，一个粗略的草图：

boolean isRepeatingPattern = false;

for (Integer factor : factors) {

    int iterations = stringSize / factor;

    String previousSubstring = stringParam.substring(0, factor); 

    for (int i = 1; i < iterations; i++) {

        int index = i * factor;

        if (previousSubstring != stringParam.substring(index, index + factor)) break;

        if (i == iterations - 1) repeatingPattern = true;

    }

}