Si una cadena T de longitud K aparece K o más veces en una cadena S , entonces es potencialmente comunista . Por ejemplo, 10in 10/10es potencialmente comunista, ya que aparece 2 veces y tiene una longitud de 2 . Tenga en cuenta que estas subcadenas no pueden solaparse.

Una transformación comunista es el que tiene esta cadena T y se mueve cada personaje t _i de T a la i ocurrencia de T en S . Entonces, para el ejemplo anterior, la transformación comunista produciría 1/0; el primer carácter de 10reemplaza 10la primera vez que 10se encuentra, y 0la segunda vez.

Una normalización comunista es una función que toma todas esas cadenas T con K ≥ 2 y realiza una transformación comunista en ellas.

Algunos detalles sobre el algoritmo:

1. Realice transformaciones comunistas en las cadenas válidas más largas T primero . Favorecer a las primeras apariciones de T .
2. Luego, realice transformaciones comunistas en las siguientes cadenas más largas, luego en la siguiente siguiente más larga ... etc.
3. Repita hasta que no existan tales cadenas en la cadena.

Tenga en cuenta que algunas cadenas, como el ejemplo "Hola, Hola" en los casos de prueba, se pueden interpretar de dos maneras diferentes. Puede usar ellpara T , pero también puede usar llo. En este caso, su código puede elegir cualquiera de las opciones. El caso de prueba que se muestra utiliza llo, pero puede obtener un resultado diferente e igualmente válido.

Su tarea es implementar la normalización comunista. La entrada solo consistirá en caracteres ASCII imprimibles (0x20 a 0x7E, espacio para tilde). Puede escribir un programa o función para resolver esta tarea; la entrada puede tomarse como una línea de STDIN, argumento de matriz de cadena / carácter, argumento de ARGV, etc.

Casos de prueba

'123' -> '123'
'111' -> '111'
'1111' -> '11'
'ABAB' -> 'AB'
'111111111' -> '111'
'asdasdasd' -> 'asd'
'10/10' -> '1/0'
'100/100+100' -> '1/0+0'
'   +   +   ' -> ' + '
'Hello, hello, dear fellow!' -> 'Hel he, dear feow!' OR 'Heo hl, dear flow!'
'11122333/11122333/11122333' -> '112/13' OR '132/23'

'ababab1ababab' -> 'a1bab'
'1ab2ab3ab4ab5ab6' -> '1a2b3a4b5ab6'

Caso de prueba resuelto

El formato es 'string', 'substring', en cada paso de reemplazo. Los bits reemplazados están entre corchetes.

'11[122]333/11[122]333/11[122]333', '122'
'111[333]/112[333]/112[333]', '333'
'1113/11[23]/11[23]', '23'
'11[13]/112/1[13]', '13'
'1[11]/[11]2/13', '11'
'1[/1]12[/1]3', '/1'
'112/13', ''

Otro caso de prueba:

'Hello, hello, dear fellow!', 'llo'
'Hel, hel, dear feow!', 'l,'
'Hel he, dear feow!', ''

Código de referencia (Python)

Puede encontrar esto útil para visualizar el algoritmo.

#!/usr/bin/env python

import re

def repeater(string):
    def repeating_substring(substring):
        return (string.count(substring) == len(substring)) and string.count(substring) > 1

    return repeating_substring

def get_substrings(string):
    j = 1
    a = set()
    while True:
        for i in range(len(string) - j+1):
            a.add(string[i:i+j])
        if j == len(string):
            break
        j += 1
    return list(a)

def replace_each_instance(string, substring):
    assert `string`+',', `substring`
    for i in substring:
        string = re.sub(re.escape(substring), i, string, 1)

    return string


def main(s):
    repeats = repeater(s)
    repeating_substr = filter(repeater(s), get_substrings(s))

    while repeating_substr:
        repeating_substr.sort(lambda x,y: cmp(len(y), len(x)))
        s = replace_each_instance(s, repeating_substr[0])
        repeating_substr = filter(repeater(s), get_substrings(s))

    return s

assert main('123') == '123'
assert main('111') == '111'
assert main('1111') == '11'
assert main('ABAB') == 'AB'
assert main('111111111') == '111'
assert main('asdasdasd') == 'asd'
assert main('10/10') == '1/0'
assert main('100/100+100') == '1/0+0'
assert main('   +   +   ') == ' + '
assert main('Hello, hello, dear fellow!') == 'Hel he, dear feow!'
assert main('11122333/11122333/11122333') == '112/13'

Gracias a @ ConorO'Brien por publicar la idea original de este desafío.

Pyth, 22 bytes

u.xse.iLcGdf>cGTlTt#.:

Banco de pruebas

Para ver realmente lo que está haciendo el programa, mira esto:

Internos

En particular, el programa siempre usa el reemplazo final de los reemplazos más largos.

Explicación:

u.xse.iLcGdf>cGTlTt#.:
u.xse.iLcGdf>cGTlTt#.:G)GQ    Implicit
u                        Q    Starting with the input, repeat the following
                              until a fixed point is reached.
                    .:G)      Construct all substrings of the current value
                              ordered smallest to largest, front to back.
                  t#          Filter on having more than 1 element.
                              These are the eligible substrings.
           f                  Filter these substrings on
             cGT              Chop the current value on the substring,
            >   lT            Then remove the first len(substring) pieces.
                              The result is nonempty if the substring is
                              one we're looking for. 
                              Chopping gives nonoverlapping occurrences.
     .iL                      Interlace the substrings with
        cGd                   Chop the current value on that substring
   se                         Take the final result, make it a string.
 .x                     G     If there weren't any, the above throws an error,
                              So keep the current value to halt.

JavaScript (ES6), 121 bytes

f=(s,j=2,o,m=s.match(`(.{${j}})(.*\\1){${(j-1)}}`))=>m?f(s,j+1,s.split(m[1]).map((e,i)=>e+(m[1][i]||'')).join``):o?f(o):s

Recurrentemente coincide con el patrón:

(.{2})(.*\1){1}  //2 characters, repeated 1 time 
(.{3})(.*\1){2}  //3 characters, repeated 2 times 
(.{4})(.*\1){3}  //4 characters, repeated 3 times 
etc.

... hasta que no se encuentre el patrón. (Esto garantiza que la cadena más larga se maneje primero).

Luego realiza las "transformaciones comunistas" en el último patrón encontrado, dividiéndose en el partido y uniéndose en cada uno de los personajes del partido. ( mapse usa para este propósito. Lástima joinque no reciba una devolución de llamada).

Finalmente vuelve a aparecer en esta nueva cadena hasta que ya no sea comunista .

Casos de prueba:

f=(s,j=2,o,m=s.match(`(.{${j}})(.*\\1){${(j-1)}}`))=>m?f(s,j+1,s.split(m[1]).map((e,i)=>e+(m[1][i]||'')).join``):o?f(o):s

console.log(f('123'));  //123
console.log(f('111'));  //111
console.log(f('1111')); //11
console.log(f('ABAB')); //AB
console.log(f('111111111')); //111
console.log(f('asdasdasd')); //asd
console.log(f('10/10')); //1/0
console.log(f('100/100+100')); //1/0+0
console.log(f('   +   +   ')); // + 
console.log(f('Hello, hello, dear fellow!')); //Heo hl, dear flow!
console.log(f('11122333/11122333/11122333')); //132/23

Limpio , 420 ... 368 bytes

import StdEnv,StdLib
l=length
%q=any((==)q)
?_[]=[]
?a[(y,x):b]|isPrefixOf a[x:map snd b]=[y: ?a(drop(l a-1)b)]= ?a b
$s=sortBy(\a b=l a>l b)(flatten[[b: $a]\\(a,b)<-map((flip splitAt)s)[0..l s-1]])
f s#i=zip2[0..]s
#r=filter(\b=l(?b i)>=l b&&l b>1)($s)
|r>[]#h=hd r
#t=take(l h)(?h i)
=f[if(%n t)(h!!hd(elemIndices n t))c\\(n,c)<-i|not(%n[u+v\\u<-t,v<-[1..l h-1]])]=s

Pruébalo en línea!