Как проверить повторение последовательности в целых числах

У меня есть алфавитно-цифровая строка, и я хочу проверить повторение шаблона в ней только для целых чисел. И они должны быть непрерывными.

Пример

12341234QQ должен сказать мне, что 1234 повторяется.
1234qwe1234 должен НЕ сказать, что 1234 повторяется, так как он не является непрерывным.
12121212 следует рассматривать как 12 повторяющихся, поскольку это первый набор, который будет найден, повторяется. Но если есть алгоритм, который найдет 1212 в качестве повторного набора до 12, я думаю, он должен снова выполнить шаги на 1212.

Я думал, что я могу хранить целую часть, итерируя и сравнивая ее с ( <= '0' && >= '9') в другом StringBuilder. Затем я читал о выполнении БПФ на строке, и он показывает повторяющиеся шаблоны. Но я понятия не имею, как выполнять FFT на Java и искать результаты, также я надеялся сделать это, не обращаясь к обработке сигналов. Я прочитал о сопоставлении шаблонов KMP, но работает только с данным вводом. Есть ли другой способ сделать это?

Ответ 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

Ответ 2

Я не уверен, знакомы ли вы с RegularExpressions (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/

Ответ 3

Моя теория заключается в том, что вы можете использовать структуру данных, известную как суффикс дерева, чтобы достичь того, чего вы хотите.

Пройдя через исходную строку, соберите каждую непрерывную последовательность цифр и постройте ее дерево суффиксов. Для вашего примера это будет выглядеть (для первых 4 суффиксов):

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

Теперь следующий суффикс в порядке будет 1234 $. Однако при вставке мы замечаем, что он соответствует префиксу 1234 первого суффикса. Счетчик поддерживается параллельно и увеличивается каждый раз, когда в дерево добавляется суффикс.

На каждом шаге мы сравниваем счетчик с длиной совпадения между текущим суффиксом, который нужно вставить, и подстрокой, с которой он совпадает. Если длина совпадения кратная счетчику, то у нас есть повторение.

В приведенном выше случае счетчик будет 4 (начиная с 0) к моменту вставки 1234 $, а длина совпадения с префиксом 12341234 $также равна 4, поэтому повторяется 1234.

Ответ 4

Сначала вы хотите определить некоторые правила для шаблона. Если шаблон может иметь любую произвольную длину, тогда вы должны начать хранить значения int (создание шаблона) и начать проверять повторение при первом повторном int.

В этом случае: 1234123q Вы создаете шаблон 1234, тогда, поскольку 1 повторяется, вы должны сохранить его и начать сравнивать его со следующими значениями.

Как вы обрабатываете повторения внутри шаблона?

В случае: 123124123124

шаблон 123124 повторяется дважды. Если он регистрируется как повторение или останавливается на первых 4 с 123!= 124?

Если вы решите зарегистрировать этот случай как допустимое повторение, вам нужно будет начать создавать параллельные шаблоны, чтобы проверять их в период времени, когда вы их наращиваете.

Первый случай (остановка при первом НЕ повторном значении) прост, второй случай будет генерировать много параболических шаблонов для сборки и проверки в одно и то же время.

Как только вы достигнете конца потока, вы можете выполнить поиск с использованием существующих методов, созданных String.

Ответ 5

Apache Commons Lang. имеет класс org.apache.commons.lang.StringUtils, который имеет метод, который учитывает вхождения конкретной подстроки. Он уже существует, поэтому вы можете использовать его напрямую, а не создавать собственное решение.

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