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

Чтобы убедиться, что других людей это не беспокоит, ваша задача - написать программу, которая решит эту проблему!

задача

Если задана строка ввода (если это имеет значение для вашего языка, вы можете предполагать ввод только для ASCII, который не содержит перевода строки.) str, Который содержит где-то посередине подстроку, которая встречается дважды подряд, вернуть строку с одним экземпляром этого подстрока удалена.

В случае множественных возможностей, верните самый короткий из возможных ответов (то есть выберите самую длинную последовательную повторяющуюся подстроку и удалите ее).

В случае нескольких одинаково длинных последовательных повторяющихся подстрок удалите первую (то есть первую, встречающуюся при чтении строки спереди назад).

Вы можете предположить, что ввод правильный (т. Е. Всегда содержит последовательную повторяющуюся подстроку), что может помочь в этом.

Примеры

1. Вход: hello hello world-> Вывод: hello world.
2. Вход: foofoo-> Вывод: foo. (Итак: Да, строка может состоять только из повторяющейся части дважды).
3. Input: aaaaa-> Output: здесь aaaнаходится самая длинная повторяющаяся последовательная подстрока aa.
4. Input: Slartibartfast-> Это недопустимый ввод, так как он не содержит последовательно повторяющейся подстроки, поэтому вам не нужно обрабатывать этот случай.
5. Ввод: the few the bar-> Это еще один неверный ввод, так как повторяющаяся часть должна следовать сразу же за исходной частью. В этом случае theи theразделяются чем-то еще между ними, поэтому этот ввод недействителен.
6. Вход: ababcbc-> Вывод: abcbc. Две возможные самые длинные последовательные повторяющиеся подстроки - это abи bc. Как abвстречалось ранее в строке, это правильный ответ.
7. Вход: Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo. Выход: Buffalo buffalo buffalo buffalo Buffalo buffalo. (Произведенная замена должна быть чувствительной к регистру).
8. Вход: Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice couple of words twice in succession.-> Вывод: Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice in succession.. Только самая длинная последовательная повторяющаяся подстрока удаляется.

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

Perl 6 , 40 байт

{.subst: m:ex/(.*))>$0/.max(*.chars),''}

Попытайся

{
  .subst:             # substitute


    m                 # match
    :exhaustive
    /
      ( .* )          # any number of chars

      )>              # don't include the following in what is returned

      $0              # the first match again
    /.max( *.chars ), # find the first longest submatch


    ''                # substitute it with nothing
}

Retina , 35 33 байта

Число байтов предполагает кодировку ISO 8859-1.

(?=(.+)(\1.*))
$2¶$`
O$#`
$.&
G1`

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

объяснение

Так как движки регулярных выражений ищут совпадения слева направо, нетривиально найти самое длинное совпадение независимо от позиции. Это можно сделать с помощью балансировочных групп .NET, но результат довольно неприятный:

1`((.)+)\1(?<=(?!.*((?>(?<-2>.)+).+)\3)^.*)
$1

Поэтому я решил, что постараюсь избежать этого, используя некоторые другие функции Retina.

(?=(.+)(\1.*))
$2¶$`

Мы начинаем с применения всех возможных подстановок, по одной на каждой строке. Для этого мы сопоставляем позицию перед совпадением (а не само совпадение), чтобы обеспечить совпадение совпадений. Это сделано, помещая реальное регулярное выражение в перспективу. Затем этот запрос захватывает оставшиеся, кроме дубликата, который мы хотим удалить в группе 2. Мы записываем обратно группу 2 (удаление дубликата), перевод строки, а затем весь ввод до совпадения, что дает нам в основном новую строку для быть замененным.

В конце у нас будет по одной строке для каждого совпадения с удалением соответствующего дубликата. В конце также будет полный ввод без каких-либо замен.

Теперь, когда у нас есть все возможные замены, мы хотим самый короткий результат (который соответствует самому длинному удаленному повторению).

O$#`
$.&

Поэтому мы сначала сортируем строки по длине.

G1`

И тогда мы оставим только первую строчку.

Желе , 22 19 байт

-2 байта благодаря Деннису (избежать перестановки аргумента, удалить слегка избыточное приращение)

ẋ2³wȧ+¥J
ẆÇ€LÐṀḢṬœp

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

Полная программа (была обнаружена ошибка, ÐṀсвязанная с неправильным действием arity над диадами, которая будет исправлена ​​в ближайшее время; хотя я не уверен, что это может привести к более короткому коду здесь).

Как?

Находит первый из самых длинных срезов ввода, так что повторение существует во входе, и удаляет его из ввода.

ẋ2³wȧ+¥J - Link 1, removal indices for given slice if valid, else 0: slice, x
ẋ2       - repeat x twice, say y
  ³      - program input: s
   w     - index of first occurrence of y in s (1-based) or 0, say i
       J - range(length(x)): [1,2,3,...,length(x)]
      ¥  - last two links as a dyad
    ȧ    -     and (non-vectorising)
     +   -     addition: [1+i,2+i,3+i,...,length(x)+i] or 0
         - note: no need to decrement these since the last index will be the 1st index
         - of the repetition (thanks to Dennis for spotting that!)

ẆÇ€LÐṀḢṬœp - Main link: string, s
Ẇ          - all sublists of s (order is short to long, left to right, e.g. a,b,c,ab,bc,abc)
 Ç€        - call the last link (1) as a monad for €ach
    ÐṀ     - filter by maximal
   L       -     length
      Ḣ    - head: get the first (and hence left-most) one
       Ṭ   - untruth: make a list with 1s at the indexes given and 0s elsewhere
        œp - partition s at truthy indexes of that, throwing away the borders
           - implicit print

JavaScript (ES6), 81 74 байта

f=
s=>s.replace(/(?=(.+)\1)/g,(_,m)=>r=m[r.length]?m:r,r='')&&s.replace(r,'')

<input oninput=o.textContent=f(this.value)><pre id=o>

Редактировать: спас 7 байтов, украв m[r.length]уловку Арно .

PowerShell , 87 байт

param($s)([regex](([regex]'(.+)\1'|% *hes $s|sort L*)[-1]|% Gr*|% V*)[1])|% Re* $s '' 1

Попробуйте онлайн! (все тесты)

объяснение

Начиная с внутренней стороны в основном, мы бежим Matchesс (.+)\1регулярным выражением, чтобы вернуть все объекты соответствия для указанной строки. Регулярное выражение соответствует любой последовательности символов, за которой следует сама.

Затем полученные объекты sortсоответствия сортируются по их Lengthсвойству (сокращенному до подстановочного знака). Это приводит к массиву совпадений, отсортированных по длине, по возрастанию, поэтому индексируйте, [-1]чтобы получить последний элемент (самый длинный). Значение этого совпадения - это совпадение, а не группа, поэтому оно включает в себя повторение, поэтому мы извлекаем объект Group ( |% Gr*), а затем значение этого ( |% V*), чтобы получить наибольшую повторяющуюся строку. Дело в том, что объект группы на самом деле является массивом, потому что группа 0 всегда совпадает, но я хочу фактическую группу (1), поэтому результирующее значение на самом деле значение s , следовательно, индексирование для получения второго элемента [1]. Это значение преобразуется в сам объект регулярного выражения, а затемReplaceметод вызывается для исходной строки, заменяется ничем, и заменяется только первое совпадение ( |% Re* $s '' 1).

Haskell , 101 байт

Основная функция f, она принимает и возвращает String.

l=length
a=splitAt
f s|i<-[0..l s-1]=[p++t|n<-i,(p,(r,t))<-fmap(a$l s-n).(`a`s)<$>i,r==take(l r)t]!!0

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

Когда я начал это, я импортировал Data.Listи используется maximum, tails, initsи isPrefixOf. Каким- то образом это превратилось в это. Но мне все же удалось только сбрить 11 байтов ...

Заметки

• splitAt/ aразбивает строку по заданному индексу.
• s является входной строкой.
• iсписок чисел [0 .. length s - 1], -1который нужно обойти, который splitAtразделяется в конце, если задан слишком большой индекс.
• nэто length sминус цель длина повторяющейся части, она выбрана таким образом , чтобы мы не должны использовать два списка номер и / или многословным уменьшая синтаксис списка.
• p, rи tявляются трехсторонним разделением s, с rпредполагаемой повторяемой частью. fmapТам использует , (,) String Functorчтобы избежать переменной для промежуточного разделения.
• !!0 выбирает первый элемент списка совпадений.

Желе , 23 21 байт

ṚẆUẋ€2ẇÐf¹ṪðLHḶ+w@Ṭœp

Спасибо @JonathanAllan за его Ṭœpидею, которая сэкономила 2 байта.

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

Mathematica, 63 60 59 байт

^{4 байта сэкономлено благодаря Мартину Эндеру .}

#&@@StringReplaceList[#,a__~~a__->a]~SortBy~{StringLength}&

Анонимная функция. Принимает строку в качестве ввода и возвращает строку в качестве вывода.

JavaScript (ES6), 70 байт

s=>s.replace(s.match(/(.+)(?=\1)/g).reduce((p,c)=>c[p.length]?c:p),'')

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

let f =

s=>s.replace(s.match(/(.+)(?=\1)/g).reduce((p,c)=>c[p.length]?c:p),'')

console.log(f("hello hello world"))
console.log(f("foofoo"))
console.log(f("aaaaa"))
console.log(f("ababcbc"))
console.log(f("Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice couple of words twice in succession."))

Это должен быть комментарий, но у меня недостаточно репутации, чтобы комментировать. Я просто хочу сказать @Neil, что его код может быть уменьшен до 77 байтов. Вам не нужно использовать прямое утверждение в регулярном выражении. Вот уменьшенная версия:

s=>s.replace(/(.+)\1/g,(_,m)=>(n=m.length)>l&&(l=n,r=m),l=0)&&s.replace(r,'')

C #, 169 байт

(s)=>{var x="";for(int i=0;i<s.Length-2;i++){for(int l=1;l<=(s.Length-i)/2;l++){var y=s.Substring(i,l);if(s.Contains(y+y)&l>x.Length)x=y;}}return s.Replace(x+x,x);}

объяснение

(s) => {                // Anonymous function declaration    
    var x = "";         // String to store the longest repeating substring found
    for (int i = 0; i < s.Length - 2; i++) {               // Loop through the input string
        for (int l = 1; l <= (s.Length - i) / 2; l++) {    // Loop through all possible substring lengths
            var y = s.Substring(i, l);
            if (s.Contains(y + y) & l > x.Length) x = y;   // Check if the substring repeats and is longer than any previously found
        }
    }
    return s.Replace(x + x, x);    // Perform the replacement
}

Это подход грубой силы: пробуйте каждую возможную подстроку, пока мы не найдем самую длинную повторяющуюся подстроку. Несомненно, Regex более эффективен, но работа с Regex в C # имеет тенденцию быть достаточно многословной.

PHP, 84 82 байта

Примечание: используется кодировка IBM-850.

for($l=strlen($argn);--$l&&!$r=preg_filter("#(.{0$l})\g-1#",~█╬,$argn,1););echo$r;

Запустите так:

echo 'hello hello world' | php -nR 'for($l=strlen($argn);--$l&&!$r=preg_filter("#(.{0$l})\g-1#",~█╬,$argn,1););echo$r;';echo
> hello world

объяснение

for(
  $l=strlen($argn);   # Set $l to input length.
  --$l   &&           # Decrement $l each iteration until it becomes 0.
  !$r=preg_filter(    # Stop looping when preg_filter has a result
                      # (meaning a successful replace).
    "#(.{0$l})\g-1#", # Find any character, $l times (so the longest
                      # match is tried first), repeated twice.
    ~█╬,              # Replace with $1: first capture group, removing the
                      # duplicate.
    $argn,
    1                 # Only replace 1 match.
  );
);
echo$r;               # Print the result of the (only) successful
                      # search/replace, if any.

Tweaks

• Сохранено 2 байта, потому что нет минимальной длины повторяющейся подстроки