Ulangi setelah saya!

23

Diberikan string sebagai argumen, hasilkan panjang substring berulang yang terpanjang atau tidak tumpang tindih atau nol jika tidak ada string tersebut.

Anda dapat menganggap string input tidak kosong.

Contohnya

abcdefabc: substring abcdiulangi pada posisi 1 dan 7, sehingga program harus menampilkan 3

abcabcabcabcab: abcabcatau bcabcaatau cabcabdiulang, sehingga program harus menampilkan 6 . (substring abcabcabcabjuga diulang, tetapi kejadiannya tumpang tindih, jadi kami tidak menerimanya).

aaaaaaa: aaadiulangi pada posisi 1 dan 4 misalnya, sehingga program harus menampilkan 3

abcda: adiulang, sehingga program harus menampilkan 1

xyz: tidak ada string berulang → 0

ababcabcabcabcab: harus mengembalikan 6

Ini adalah , byte paling sedikit menang.

Arnaud
sumber
1
Mungkinkah senarnya kosong? Jika itu masalahnya, apakah akan diizinkan untuk menghasilkan False daripada 0 ?
Dennis
@ Dennis Anda dapat menganggap string tidak kosong.
Arnaud

Jawaban:

9

brainfuck, 226 byte

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

Diformat:

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

Mengharapkan input dengan atau tanpa baris baru, dan menampilkan hasilnya sebagai nilai byte .

Cobalah online.

Ini memeriksa setiap awalan untuk melihat apakah itu terjadi kemudian dalam string, lalu memangkas karakter pertama dan mengulangi proses sampai tidak ada lagi karakter yang tersisa.

Rekaman itu dibagi menjadi 3-sel node,

c 0 f

di mana ckarakter dari string yang diberikan, dan fmerupakan bendera yang dapat berupa salah satu, negatif, atau nol. Bendera bukan-nol ditempatkan di antara dua karakter yang saat ini dibandingkan, dan yang negatif dicadangkan untuk sel setelah akhir awalan saat ini dan sebelum awal akhiran saat ini (yaitu, sebelum indeks pertandingan potensial saat ini).

Hasilnya disimpan di sebelah kiri string dan diperbarui setiap kali kecocokan ditemukan.

(String sebenarnya diproses secara terbalik dengan \x01menambahkannya.)

Mitch Schwartz
sumber
6

Jelly , 12 byte

œ-QL€
ŒṖÇ€FṀ

Cobalah online!

Bagaimana itu bekerja

ŒṖÇ€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. 
Dennis
sumber
1
Semua hujan es Jelly, bahasa golf kode pamungkas!
Nissa
œ-Qsangat rapi.
Lynn
5

Perl 6 , 36 byte

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

Cobalah

Diperluas:

{   # 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

}
Brad Gilbert b2gills
sumber
5

Retina , 35 32 30 byte

Tantangan yang cukup keren.

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

Cobalah online

Penjelasan:

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
sumber
Anda dapat menyimpan dua byte dengan menggunakan M%`.sebagai tahap kedua.
Martin Ender
4

JavaScript (ES6), 79 68 66 byte

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>

Sunting: Disimpan 11 13 byte berkat @Arnauld.

Neil
sumber
4

Haskell , 79 byte

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

Cobalah online!

Wisaya Gandum
sumber
2
Sepertinya argumen pertama dari %dapat mengakumulasi urutan yang tidak bersebelahan, memberikan positif palsu seperti 2 untuk aadalam axayaa,
xnor
Apa yang dikatakan @xnor. Saya pikir panggilan rekursif a%dsalah, tetapi juga tidak perlu. Yang juga berarti Anda dapat menggunakan maxbukan maximum.
Ørjan Johansen
1
Saya pikir mengubah a%duntuk ""%dmemperbaikinya.
xnor
Oh benar, masih diperlukan (dan suara) ketika akosong.
Ørjan Johansen
1
Saya pikir sum[1|(x,y)<-zip a c,x==y]bisa digunakan sebagai gantinya a!c.
Laikoni
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
sumber
2

Sekam , 11 byte

L►L§fo↓2`xQ

Cobalah online!

Catatan: Sekam lebih baru dari tantangan ini.

Penjelasan

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
sumber
2

Perl 5 dengan -p, 40 byte

$_+=(sort map{y///c}/(?=(.+).*\1)/g)[-1]

Cobalah online!

Dom Hastings
sumber
1

Mathematica, 75 65 byte

10 byte disimpan karena @JingHwan Min .

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

Fungsi anonim. Mengambil string sebagai input, dan mengembalikan angka sebagai output.

LegionMammal978
sumber
Saya tidak berpikir Anda perlu awal dan akhir BlankNullSequence (___)kapan Overlaps->Allada. Max@StringLength@StringCases[#,a___~~___~~a___:>a,Overlaps->All]&akan baik-baik saja.
JungHwan Min
@JungHwanMin Terima kasih, membingungkannya dengan StringReplace: P
LegionMammal978
1

Pyth - 16 byte

Saya perlu golf mengubah semua string menjadi panjang dan menemukan maks.

eSlM+ksmft/dTd./

Test Suite .

Maltysen
sumber
1

Clojure, 112 byte

#(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)))))

loop dua kali dari angka 0ken - 1 ( nmenjadi panjang string), menjatuhkan jkarakter dan membagi sisanya menjadi bagian "awal" dan "akhir". Membuat satu set semua substring dengan epanjang bdan menggunakannya sebagai fungsi untuk memeriksa apakah bditemukan dari sana. Mengembalikan panjang bjika ditemukan dan 0 jika tidak, mengembalikan maks dari nilai-nilai ini.

Akan menarik melihat versi yang lebih pendek.

NikoNyrh
sumber
1

Retina , 24 byte

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

Cobalah online!

Sebuah pemanasan bagi saya untuk mempelajari fitur-fitur baru dari Retina 1.

Penjelasan

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

Tahap Daftar, ini mengembalikan semua kecocokan untuk regex (.*).*\1, yang cocok dengan pola apa pun dari bentuk "ABA", di mana A dan B adalah dua substring sewenang-wenang (mungkin kosong). Opsi tambahan yang diberikan untuk tahap ini adalah v, yang mempertimbangkan pertandingan yang tumpang tindih, dan $yang menerapkan substitusi pada masing-masing pertandingan sebelum mengembalikannya: substitusi ditunjukkan pada baris kedua, dan sesuai dengan panjang ( .) dari grup penangkap pertama ( yang akan menjadi substring "A" pada contoh sebelumnya).

N`

Kami sekarang memiliki semua panjang substring berulang, tahap ini hanya mengurutkannya dalam urutan numerik, dari yang terpendek ke yang terpanjang.

G-1`

Akhirnya, tahap grep ini ( G) hanya menyimpan hasil terakhir ( -1), yang merupakan panjang dari substring terpanjang yang diulang.

Leo
sumber
0

Javascript, 165 byte

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}

Uji Kasus

console.log(a('abcabcabcabc')) // Output 6
console.log(a('xyz'))          // Output 0
console.log(a('aaaaaaa'));     // Output 3
console.log(a('abcdefabc'));   // Output 3
Lalith Prasad
sumber
2
Selamat datang di Programming Puzzles & Code Golf. Sayangnya, ini mengembalikan 2 untuk input ababcabcabcabcab, tetapi string cabcabdiulang.
Dennis