Повторяй за мной!

23

Задав строку в качестве аргумента, выведите длину самой длинной (-ых) непересекающейся повторной подстроки (-ов) или ноль, если такой строки нет.

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

Примеры

abcdefabc: подстрока abcповторяется в позициях 1 и 7, поэтому программа должна вывести 3

abcabcabcabcab: abcabcили bcabcaили cabcabповторяются, поэтому программа должна вывести 6 . (подстрока abcabcabcabтакже повторяется, но вхождения перекрываются, поэтому мы не принимаем это).

aaaaaaa: aaaповторяется, например, в позициях 1 и 4, поэтому программа должна вывести 3

abcda: aповторяется, поэтому программа должна вывести 1

xyz: нет повторяющейся строки → 0

ababcabcabcabcab: должен вернуться 6

Это код-гольф , поэтому побеждает меньше байтов.

code-golf string code-golf code-golf kolmogorov-complexity primes code-golf kolmogorov-complexity hexadecimal code-golf code-golf string code-golf string random code-golf array-manipulation code-golf ascii-art kolmogorov-complexity random code-golf array-manipulation code-golf stateful code-golf hello-world code-golf string code-golf interpreter lisp code-golf restricted-source quine palindrome code-golf ascii-art random generation challenge-writing ascii-art random polyglot maze answer-chaining string cops-and-robbers whitespace code-golf string cops-and-robbers whitespace code-golf number sequence code-golf date code-golf ascii-art decision-problem code-golf combinatorics chemistry code-golf kolmogorov-complexity source-layout radiation-hardening code-golf ascii-art path-finding maze code-golf string ascii-art game animation code-golf string ascii-art code-golf ascii-art kolmogorov-complexity code-golf restricted-source new-years Arnaud
источник
1
Может ли строка быть пустой? Если это так, будет ли разрешено выводить False, а не 0 ?
Деннис
@ Денис Вы можете предположить, что строка не пуста.
Арно

Ответы:

9

брейкфак, 226 байт

,[<<<,]+[>>->[[[[>>[>>>]<+<-<[<<<]>>+<-]>[<+>-]>[>>>]<<[>[<+>-]]>[[<+>-]>+[<<<]>
>>-[+>[<<<]<[>+>[->]<<[<]>-]>[<+>>+<-]>>>[>>>]]>>]<]>+[,<<<+]->[<<<]>>>>>+[,+>>>
+]-[>>>]->]<[+<<<]+<<<++[->>>]+>>>->]<[,<<<]<[>>>+<<<-]>+>,>>>]<<.

отформатирован:

,[<<<,]
+
[
  for each suffix
  >>->
  [
    for each prefix
    [
      for each suffix
      [
        for each char while no mismatch
        [
          >>[>>>]
          <+<-<[<<<]
          > >+<-
        ]
        >[<+>-]
        >[>>>]
        <<
        [
          mismatch
          >[<+>-]
        ]
        >
        [
          [<+>-]
          >+[<<<]
          >>>-
          [
            match
            +>[<<<]
            <
            [
              >+>[->]
              <<[<]
              >-
            ]
            >[<+> >+<-]
            >>>[>>>]
          ]
          >>
        ]
        <
      ]
      >+[,<<<+]
      ->[<<<]
      >>> >>+[,+>>>+]
      -[>>>]
      ->
    ]
    <[+<<<]
    +<<<++[->>>]
    +>>>->
  ]
  <[,<<<]
  <[>>>+<<<-]
  >+>,>>>
]
<<.

Ожидает ввод с или без завершающего символа новой строки и выводит результат в виде байтового значения .

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

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

Лента разделена на 3-ячеечные узлы,

c 0 f

где c- символ данной строки, и fэто флаг, который может быть либо единичным, либо отрицательным, либо нулевым. Ненулевые флаги помещаются между двумя сравниваемыми символами, а отрицательные зарезервированы для ячеек после конца текущего префикса и перед началом текущего суффикса (т. Е. Перед индексом текущего потенциального совпадения).

Результат сохраняется слева от строки и обновляется всякий раз, когда найдено совпадение.

(Строка фактически обрабатывается в обратном порядке с \x01добавлением к ней.)

Митч Шварц
источник
6

Желе , 12 байт

œ-QL€
ŒṖÇ€FṀ

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

Как это работает

ŒṖÇ€FṀ  Main link. Argument: s (string)

ŒṖ      Generate all partitions of s.
  ǀ    Apply the helper link to each partition.
    F   Flatten the resulting array of lengths.
     Ṁ  Take the maximum.


œ-QL€   Helper link. Argument: P (partition)

  Q     Yield the elements of P, deduplicated.
œ-      Multiset subtraction; remove exactly one occurrence of each string in P.
   L€   Compute the lengths of the remaining strings.
Деннис
источник
1
Приветствую Желе, лучший язык для игры в гольф!
Nissa
œ-Qдействительно опрятно.
Линн
5

Perl 6 , 36 байт

{m:ex/(.*).*$0/.map(*[0].chars).max}

Попытайся

Expanded:

{   # bare block lambda with implicit parameter ｢$_｣

  m           # match ( implicitly against ｢$_｣
  :exhaustive # every possible way
  /
    (.*)      # any number of characters ( stored in ｢$0｣ )
    .*
    $0
  /

  .map(

    *\        # the parameter to Whatever lambda
    [0]\      # the value that was in ｢$0｣ for that match
    .chars    # the number of characters

  ).max

}
Брэд Гилберт b2gills
источник
5

Retina , 35 32 30 байт

Довольно крутой вызов.

M&!`(.*)(?=.*\1)
M%`.
O#^`
G1`

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

Объяснение:

M&!`(.*)(?=.*\1)    # Prints overlapping greedy substrings occuring more than once
M%`.                # Replace each line with its length
O#^`                # Sort lines by number in reverse
G1`                 # Return the first line
mbomb007
источник
Вы можете сохранить два байта, используя M%`.в качестве второго этапа.
Мартин Эндер
4

JavaScript (ES6), 79 68 66 байт

f=(s,r,l=s.match(/(.*).*\1/)[1].length)=>s?f(s.slice(1),l<r?r:l):r
<input oninput=o.textContent=f(this.value)><pre id=o>
Развернуть фрагмент

Редактировать: Сохранено 11 13 байт благодаря @Arnauld.

Нил
источник
4

Haskell , 79 байтов

(""%)
(a:b)!(c:d)|a==c=1+b!d
_!_=0
a%c@(e:d)=maximum[a!c,""%d,(a++[e])%d]
_%_=0

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

Мастер пшеницы
источник
2
Похоже, что первый аргумент %может накапливать несмежную подпоследовательность, давая ложные срабатывания, такие как 2 для aain axayaa,
xnor
Что сказал @xnor Я думаю, что рекурсивный вызов a%dнеправильный, но также и ненужный. Что также означает, что вы можете использовать maxвместо maximum.
Эрджан Йохансен,
1
Я думаю, что изменение, a%dчтобы ""%dисправить это.
xnor
Ах да, это все еще необходимо (и звук), когда aпусто.
Орджан Йохансен,
1
Я думаю, что sum[1|(x,y)<-zip a c,x==y]можно использовать вместо a!c.
Лайкони
2

JavaScript, 120 

function r(a,b,m){return b=-~b,t=a.slice(0,b),n=a.indexOf(t,b),m=b>m&&!~n?m:b,a!=t&&r(a,b,m)||(a?r(a.slice(1),m,m):~-m)}
C5H8NNaO4
источник
2

Шелуха , 11 байт

L►L§fo↓2`xQ

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

Примечание: шелуха новее, чем этот вызов.

объяснение

L►L§fo↓2`xQ  Implicit input, say x = "ababc"
          Q  Nonempty substrings: ["a","b","ab",..,"ababc"]
    f        Keep those that satisfy this:
              Take s = "ab" as an example.
   §    `x    Split x along s: ["","","c"]
     o↓2      Drop the first two pieces: ["c"]
              This is truthy (i.e. nonempty).
             Result is ["a","b","ab","a","b","ab"]
 ►L          Take element with maximal length: "ab"
             If the list is empty, "" is used instead.
L            Length: 2
Zgarb
источник
1

Mathematica, 75 65 байт

10 байтов сохранено благодаря @JingHwan Мин .

Max@StringLength@StringCases[#,a___~~___~~a___:>a,Overlaps->All]&

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

LegionMammal978
источник
Я не думаю, что вам нужно начало и конец, BlankNullSequence (___)когда Overlaps->Allесть. Max@StringLength@StringCases[#,a___~~___~~a___:>a,Overlaps->All]&было бы просто отлично.
JungHwan Мин
@JungHwanMin Спасибо, перепутал это с StringReplace: P
LegionMammal978
1

Pyth - 16 байт

Мне нужно сыграть в гольф, преобразовав все струны в длину и найдя максимум.

eSlM+ksmft/dTd./

Тестовый пакет .

Maltysen
источник
1

Clojure, 112 байт

#(apply max(for[R[(range(count %))]j R i R](let[[b e](split-at i(drop j %))](if((set(partition i 1 e))b)i 0)))))

петли дважды над числами 0до n - 1( nвремени длины строки), капли jсимволов и расщепляет остаток в «начало» и «конец» часть. Создает набор всех подстрок eдлины bи использует его как функцию, чтобы проверить, bнайден ли оттуда. Возвращает длину, bесли найдено, и 0 в противном случае, возвращает максимум этих значений.

Было бы интересно увидеть более короткую версию.

NikoNyrh
источник
1

Сетчатка , 24 байта

L$v`(.*).*\1
$.1
N`
G-1`

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

Разминка для меня, чтобы узнать новые функции Retina 1.

объяснение

L$v`(.*).*\1
$.1

Этап List, который возвращает все совпадения для регулярного выражения (.*).*\1, которые соответствуют любому шаблону формы "ABA", где A и B - две произвольные подстроки (возможно, пустые). Дополнительные параметры, заданные на этом этапе v, учитывают перекрывающиеся совпадения и $применяют подстановку к каждому совпадению перед его возвратом: подстановка указывается во второй строке и соответствует length ( .) первой группы захвата ( которая будет подстрокой "A" в предыдущем примере).

N`

Теперь у нас есть все длины повторяющихся подстрок, эта стадия просто сортирует их в числовом порядке, от самой короткой до самой длинной.

G-1`

Наконец, этот этап grep ( G) сохраняет только результат last ( -1), который является длиной самой длинной повторяющейся подстроки.

Лео
источник
0

Javascript, 165 байт

function a(s){var l=s.length/2,z=1,f='';while(z<=l){var t=s.substr(0,z),c=0;for(var i=0;i<s.length;i++){if(s.substr(i,z)===t){c++;if(c>1){f=t}}}z++}return f.length}

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

console.log(a('abcabcabcabc')) // Output 6
console.log(a('xyz'))          // Output 0
console.log(a('aaaaaaa'));     // Output 3
console.log(a('abcdefabc'));   // Output 3
Лалит Прасад
источник
2
Добро пожаловать в Программирование Пазлов и Код Гольф. К сожалению, это возвращает 2 для ввода ababcabcabcabcab, но строка cabcabповторяется.
Деннис