如何检查整数重复序列

一尘不染

如何检查整数重复序列

java

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

例

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

我以为我可以通过迭代并将其与( <= '0' && >= '9')另一个整数进行比较来存储整数部分StringBuilder。然后，我读到有关在字符串上执行FFT的知识，它显示了重复的模式。但是我不知道如何在Java中执行FFT并寻找结果，我也希望尝试这样做而不去进行信号处理。我读到有关KMP模式匹配的信息，但这仅适用于给定的输入。还有其他方法吗？

阅读 194

2020-12-03

共1个答案

一尘不染

您可以寻求正则表达式的帮助来解决此问题。考虑这样的代码：

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

2020-12-03