Если строка T длиной K появляется K или более раз в строке S , то она потенциально коммунистическая . Например, 10в 10/10потенциально коммунистическом, ибо она появляется 2 раза и имеет длину 2 . Обратите внимание, что эти подстроки не могут перекрываться.

Коммунистическое преобразование является тот , который принимает эту строку T и перемещает каждый символ т _I из Т к я вхождению Т в S . Таким образом, в предыдущем примере коммунистическая трансформация принесла бы результат 1/0; первый символ 10заменяет 10первый раз 10, найденный, а 0второй раз.

Коммунистическая нормализация это функция , которая принимает все такие строки T с K ≥ 2 и выполняет коммунистическое преобразования на них.

Некоторые особенности алгоритма:

1. Выполнение преобразований на коммунистические длиннейших действительные строки T первыми . Favor первые вхождения Т .
2. Затем выполните коммунистические преобразования для следующих самых длинных строк, затем следующего, следующего самого длинного ... и т. Д.
3. Повторяйте, пока в строке нет таких строк.

Обратите внимание, что некоторые строки, такие как пример «Hello, Hello» в тестовых примерах, могут интерпретироваться двумя различными способами. Вы можете использовать ellдля T , но вы также можете использовать llo. В этом случае ваш код может выбрать любой вариант. Показанный тестовый пример использует llo, но вы можете получить другой и одинаково действительный вывод.

Ваша задача - осуществить коммунистическую нормализацию. Ввод будет состоять только из печатных символов ASCII (от 0x20 до 0x7E, пробел до тильды). Вы можете написать программу или функцию для решения этой задачи; входные данные могут быть приняты в виде строки из STDIN, аргумента массива строки / символа, аргумента из ARGV и т. д.

Контрольные примеры

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

Разработан тестовый кейс

Формат есть 'string', 'substring', на каждом этапе замены. Замененные биты заключены в скобки.

'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', ''

Еще один тестовый пример:

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

Справочный код (Python)

Вы можете найти это полезным для визуализации алгоритма.

#!/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'

Спасибо @ ConorO'Brien за публикацию оригинальной идеи этой задачи.

Pyth, 22 байта

u.xse.iLcGdf>cGTlTt#.:

Тестирование

Чтобы действительно увидеть, что делает программа, проверьте это:

Внутренности

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

Объяснение:

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 байт

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

Рекурсивно соответствует шаблону:

(.{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.

... пока шаблон не найден. (Это гарантирует, что самая длинная строка обрабатывается первой.)

Затем он выполняет «коммунистические преобразования» на последнем найденном шаблоне, разделяя его на соответствие и присоединяясь к каждому из символов матча. ( mapиспользуется для этой цели. Жаль, joinчто не принимает обратный вызов.)

Наконец, он возвращается к этой новой строке, пока не перестанет быть коммунистическим .

Тестовые случаи:

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

Чисто , 420 ... 368 байт

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

Попробуйте онлайн!