java - 如何检查整数中的重复序列

Question

我有一个字母数字字符串，我想检查其中的模式重复是否只是整数。它们应该是连续的。

例子

12341234q我们应该告诉我1234重复了。
1234qwe1234不应该告诉我1234是重复的，因为它不连续。
12121212应该被视为12被重复，因为这是第一个被发现被重复的集合。但是，如果有一种算法可以找到1212作为12之前的重复集，那么我猜它必须在1212上再次执行这些步骤。

我的想法是我可以通过迭代存储整数部分并将其与( <= '0' && >= '9')不同的StringBuilder. 然后我读到了关于对字符串执行 FFT 的文章，它显示了重复的模式。但是我不知道如何在 Java 中执行 FFT 并寻找结果，而且，我希望在不去信号处理的情况下尝试这样做。我阅读了有关 KMP 模式匹配的信息，但这仅适用于给定的输入。有没有其他方法可以做到这一点？

score 58 · Accepted Answer

我认为你可以借助正则表达式来解决这个问题。考虑这样的代码：

String arr[] = {"12341234abc", "1234foo1234", "12121212", "111111111", "1a1212b123123c12341234d1234512345"};
String regex = "(\\d+?)\\1";
Pattern p = Pattern.compile(regex);
for (String elem : arr) {
    boolean noMatchFound = true;
    Matcher matcher = p.matcher(elem);
    while (matcher.find()) {
        noMatchFound = false;
        System.out.println(elem + " got repeated: " + matcher.group(1));
    }
    if (noMatchFound) {
        System.out.println(elem + " has no repeation");
    }
}

输出：

abc12341234abc got repeated: 1234
1234foo1234 has no repeation
12121212 got repeated: 12
12121212 got repeated: 12
111111111 got repeated: 1
111111111 got repeated: 1
111111111 got repeated: 1
111111111 got repeated: 1
1a1212b123123c12341234d1234512345 got repeated: 12
1a1212b123123c12341234d1234512345 got repeated: 123
1a1212b123123c12341234d1234512345 got repeated: 1234
1a1212b123123c12341234d1234512345 got repeated: 12345

解释：

使用的正则表达式在(\\d+?)\\1哪里

\\d        - means a numerical digit
\\d+       - means 1 or more occurrences of a digit
\\d+?      - means reluctant (non-greedy) match of 1 OR more digits
( and )    - to group the above regex into group # 1
\\1        - means back reference to group # 1
(\\d+?)\\1 - repeat the group # 1 immediately after group # 1

score 7 · Accepted Answer

我不确定您是否熟悉正则表达式 (RegEx)，但此代码有效

String str = "12341234qwe";
String rep = str.replaceAll(".*(.+)\\1.*","$1");
if (rep.equals(str))
    System.out.println(str+" has no repition");
else
    System.out.println(str+" has repition "+rep);
str = "1234qwe1234";
rep = str.replaceAll(".*(.+)\\1.*","$1");
if (rep.equals(str))
    System.out.println(str+" has no repition");
else
    System.out.println(str+" has repition "+rep);

这是教程：http ://docs.oracle.com/javase/tutorial/essential/regex/

score 6 · Accepted Answer

我的理论是，您可以使用称为后缀树的数据结构来实现您想要的。

遍历初始字符串，收集每个连续的数字序列并构建其后缀树。对于您的示例，它看起来像（对于前 4 个后缀）：

                  R - root
      |         |          |         |
      |         |          |         |
      |         |          |         | 
  12341234$  2341234$   341234$     41234$

现在，按顺序排列的下一个后缀是 1234$。但是，在插入时，我们注意到它与第一个后缀的前缀 1234 匹配。每次将后缀添加到树时，计数器都会保持并行并递增。

在每一步，我们都会将计数器与要插入的当前后缀与其匹配的子字符串之间的匹配长度进行比较。如果匹配的长度是计数器的倍数，那么我们就有重复。

在上述情况下，当我们插入 1234$ 时，计数器将是 4（从 0 开始），并且前缀为 12341234$ 的匹配长度也是 4，因此重复 1234。

score 3 · Accepted Answer

首先，您需要为模式定义一些规则。如果模式可以具有任意长度，那么您应该开始存储 int 值（构建模式）并开始检查第一个重复 int 处的重复。

在这种情况下： 1234123q 您正在构建 1234 模式，然后由于 1 重复，您应该继续存储它并开始将其与下一个值进行比较。

你如何处理模式中的重复？

案例：123124123124

模式 123124 重复两次。它应该注册为重复，还是停在自 123 != 124 以来的前 4 个？

如果您选择将这些案例注册为有效重复，则需要开始创建并行模式以在您不断构建它们的同时进行检查。

第一种情况（在第一个 NOT 重复值处停止）很简单，第二种情况将生成大量并行模式来构建和同时检查。

一旦到达流的末尾，您就可以使用字符串提供的现有方法进行搜索。

score -5 · Accepted Answer

阿帕奇公共朗。有一个类org.apache.commons.lang.StringUtils，它有一个计算特定子字符串出现次数的方法。它已经存在，因此您可以直接使用它，而不是创建自己的解决方案。

//First parameter is the string to find and second param is the String to search.
StringUtils.CountMatches("1234","12341234");

java - 如何检查整数中的重复序列

5 回答 5

解释：

Related

Reference