java - sentencia - Cómo comprobar la secuencia de repetición en un entero

repetir en java netbeans

Question

Tengo una cadena alfanumérica y quiero comprobar si hay repetición de patrón solo para los enteros. Y deberían ser continuos.

Ejemplo

1. 12341234qwe debe decirme 1234 se repite.
2. 1234qwe1234 NO debe decirme que 1234 se repite ya que no es continuo.
3. 12121212 debe tratarse como si se repitiera 12, ya que es el primer conjunto en el que se encontrará que se repite. Pero si hay un algoritmo que encontraría 1212 como el conjunto repetido antes de 12, entonces supongo que tiene que realizar los pasos nuevamente en 1212 .

Lo que pensé era que puedo almacenar la parte entera al iterarla y compararla con ( <= ''0'' && >= ''9'') en un StringBuilder diferente. Luego leí sobre la ejecución de FFT en la cadena y muestra los patrones repetidos. Pero no tengo idea de cómo realizar FFT en Java y buscar los resultados, también, esperaba intentar hacer esto sin tener que ir al Procesamiento de señales. Leí sobre la coincidencia de patrones KMP pero eso solo funciona con una entrada dada. Hay alguna otra manera de hacer esto?

Answer 1

Mi teoría es que puedes usar la estructura de datos conocida como árbol de sufijos para lograr lo que quieres.

Al pasar por la cadena inicial, recopile cada secuencia contigua de dígitos y genere su árbol de sufijos. Para su ejemplo, se vería como (para los primeros 4 sufijos):

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

Ahora, el siguiente sufijo en orden sería 1234 $. Sin embargo, cuando se inserta, notamos que coincide con el prefijo 1234 del primer sufijo. Un contador se mantiene en paralelo y se incrementa cada vez que se agrega un sufijo al árbol.

En cada paso, comparamos el contador con la longitud de la coincidencia entre el sufijo actual que se insertará y la subcadena con la que coincide. Si la duración del partido es un múltiplo del contador, entonces tenemos una repetición.

En el caso anterior, el contador sería 4 (comenzando desde 0) en el momento en que insertamos 1234 $ y la duración de la coincidencia con el prefijo de 12341234 $ también es 4, por lo que se repite 1234.

Answer 2

No estoy seguro de si está familiarizado con las expresiones regulares (RegEx) pero este código funciona

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

Aquí está el tutorial: http://docs.oracle.com/javase/tutorial/essential/regex/

Answer 3

Primero querrías definir algunas reglas para un patrón. Si un patrón puede tener una longitud arbitraria, entonces debe comenzar a almacenar valores int (creando el patrón) y comenzar a verificar si hay una repetición en el primer int repetido.

En este caso: 1234123q Usted está creando el patrón 1234, luego, como se repite 1, debe seguir almacenándolo Y comenzar a compararlo con los siguientes valores.

¿Cómo manejas las repeticiones dentro de un patrón?

En el caso: 123124123124

El patrón 123124 se repite dos veces. ¿Debería registrarse como una repetición, o detenerse en los primeros 4 desde 123! = 124?

Si elige registrar esos casos como repeticiones válidas, deberá comenzar a crear patrones paralelos para verificarlos a la vez que los construye.

El primer caso (detenerse en el primer valor NO repetido) es simple, el segundo caso generará una gran cantidad de patrones parralel para construir y verificar al mismo tiempo.

Una vez que llegue al final del flujo, podrá realizar la búsqueda utilizando los métodos existentes proporcionados por String.

Answer 4

Puedes tomar la ayuda de expresiones regulares para resolver esto, creo. Considere el código como este:

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

SALIDA:

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

Explicación:

El uso de expresiones regulares es (//d+?)//1 donde

//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

Answer 5

Apache Commons Lang. tiene una clase org.apache.commons.lang.StringUtils que tiene un método que cuenta las ocurrencias de la subcadena específica. Ya existe, por lo que puede usarlo directamente en lugar de crear su propia solución.

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