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

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

Пример

  • 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");