Sebuah string dapat dipasangkan jika dapat dipecah menjadi subtring, yang masing-masing adalah string yang diulang dua kali berturut-turut. Misalnya, aabaaababbbabadapat dipasangkan sebagai:

aaba aaba
b b
ba ba

Diberikan string a'dan b' tidak kosong , mengeluarkan nilai Kebenaran jika itu dapat dipasangkan dan nilai Falsey jika tidak.

Dipasangkan:

aa
abaaba
bbababbb
aabaaababbbaba
babababa
bbbbbbbbbbbb
aaababbabbabbbababbaabaabaababaaba
aaaabaab

Tidak dapat dipasangkan:

a
ba
baab
abaabaaba
bbbbbbbbbbbbbbb
baababbabaaaab
aaaaabbaaaaa

Saya mendorong Anda untuk datang dengan solusi berbasis non-regex bahkan ketika sudah ada jawaban regex yang lebih pendek dalam bahasa Anda. Anda dapat menandai mereka sebagai "tanpa regex". Dengan regex, maksud saya subsistem pencocokan pola string bawaan.

Papan peringkat:

var QUESTION_ID=98252,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/98252/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Python 2, 68 63 byte

f=lambda s,n=1:s==2*s[:n]or''<s[n:]>-f(s,n+1)<f(s[n:])*f(s[:n])

Pengembalian Benar atau Salah . Uji di Ideone .

Retina , 11 byte

^((.+)\2)+$

Coba semua test case. Dua byte pertama membuatnya multi-line.

Interpretasi harfiah dari aturan, jelas menggunakan regex, seperti semua program Retina akan.

Jelly , 10 byte

ẆŒPẋ€€2F€ċ

Tidak tepat efisien ... Coba online!

Bagaimana itu bekerja

ẆŒPẋ€€2F€ċ  Main link. Argument: s (string)

Ẇ           Window, generate the array of all substrings of s.
 ŒP         Powerset; generate all subarrays of substrings of s.
   ẋ€€2     Repeat each substring in each subarray twice.
            For example, ["ab", "a", "b"] becomes ["abab", "aa", "bb"].
       F€   Flatten the subarrays by concatenating their strings.
         ċ  Count how many times s appears in the generated strings.

Haskell, 72 69 byte (tidak ada regex)

g(a:b:c)|a==b=g c
g x=x==[]
any(g.words.concat).mapM(\c->[[c],c:" "])

Pendekatan brute-force. Cobalah di Ideone .

Berkat BlackCap untuk -3 byte.

Penjelasan

Fungsi helper gmengambil daftar string, dan memeriksa apakah itu terdiri dari pasangan string yang identik, seperti ["aa","aa","bba","bba","ab","ab"]. Fungsi utama (anonim) membagi string dengan semua cara yang mungkin, dan memeriksa bahwa setidaknya satu pemisahan menghasilkan daftar yangg menerima.

g(a:b:c)                                  g on list with elements a, b and tail c,
        |a==b                              in the case that a==b,
             =g c                          recurses to the tail c.
g x=                                      g on any other list x
    x==[]                                  checks that x is empty.
                                           This includes the case where a is not equal
                                           to b, resulting in False.
any(g.words.concat).mapM(\c->[[c],c:" "]) The main function:
                    mapM(\c->[[c],c:" "])  Replace each letter c with either "c" or "c "
                                           in all possible ways, return list of results.
any(              ).                       Check that at least one result satisfies this:
            concat                          Concatenate the 1- or 2-letter strings,
      words.                                split again at each space,
    g.                                      apply g.

Python 2, 60 byte

f=lambda s,t='':''<s>f(s[1:],t+s[0])|f(t and s)*f(t)>-(s==t)

Saya harap ini benar. Ini berjalan sangat lambat dan andtidak terlihat optimal.

Jelly , 12 byte

ŒṖµœs€2ZEµ€S

Dua byte lebih lama dari jawaban saya yang lain , tetapi pendekatan ini jauh lebih efisien dan menangani semua kecuali satu dari kasus uji.

Cobalah online!

Bagaimana itu bekerja

ŒṖµœs€2ZEµ€S  Main link. Argument: s (string)

ŒṖ            Generate all partitions of s.
  µ      µ€   Map the monadic chain between the µ's over the partitions.
   œs€2         Split each string in the partition into two chunks of equal length.
       Z        Zip/transpose, collecting the first halves in one array and the
                second halves in another.
        E       Test the arrays of halves for equality.
           S  Return the sum of the results, counting the number of different
              ways s can be paired.

Pyth - Tanpa Regex - 13 12 byte

Periksa apakah ada partisi yang terdiri dari semua string yang sama satu sama lain ketika dicincang menjadi dua.

sm.AqMcL2d./

Test Suite .

Brachylog , 14 byte (tanpa regex)

lye~l:1j@2zcc?

Cobalah online!

Ini terlalu lambat untuk beberapa kasus uji

Penjelasan

ly                  The list [0, …, length(Input)]
  e~l               A list whose length is an element of the previous list
     :1j            Append itself to this list
        @2zc        Split in half, zip and concatenate so that the list contains pairs of
                      consecutive identical elements
            c?      The concatenation of that list must result in the Input

JavaScript (ES6), tanpa regexp, 75 74 byte

f=s=>!s|[...s].some((_,i)=>i&&s[e='slice'](0,i)==s[e](i,i+=i)&&f(s[e](i)))

Pengembalian 1untuk dipasangkan sebaliknya 0. Sunting: Disimpan 1 byte berkat @ edc65.

Python, 58 byte

f=lambda s,p='':s>''and(f(p)>-(s==p)<f(s))|f(s[1:],p+s[0])

Ini didasarkan pada metode rekursif Dennis . Trik negasi Boolean diambil dari sana juga.

Gagasan baru adalah untuk mengulangi partisi (p,s)string asli dengan mulai ('',s)dan berulang kali memindahkan karakter pertama smenjadi karakter terakhir p. Hal ini memungkinkan bagian-bagian untuk dirujuk secara langsung tanpa mengiris tali. Tetapi, karena partisi dimulai dengan pkosong, kita harus berhati-hati untuk menghindari loop f(s)panggilan yang tak terbatas f(s).

JavaScript (ES6), 24 byte

x=>/^((.+)\2)+$/.test(x)

Mungkin tidak lebih pendek dari ini.

PHP, 40 Bytes

mencetak 0 untuk false dan 1 untuk true

<?=preg_match("#^((.+)\\2)+$#",$argv[1]);

Python, 66 64 byte

Terima kasih @Zgarb untuk -1 byte!

f=lambda x,s=1:x>x[:s]and(x==2*x[:s])|f(x[:s])&f(x[s:])|f(x,s+1)

Pengembalian Trueatau False.

Cobalah online!

Bantuan golf apa pun akan sangat dihargai.

Racket 230 byte

(let((sl string-length)(ss substring))(if(odd?(sl s))(printf ".~n")(begin(let p((s s))(if(equal? s "")(printf "!")
(for((i(range 1(add1(/(sl s)2)))))(when(equal?(ss s 0 i)(ss s i(* 2 i)))(p(ss s(* 2 i)(sl s)))))))(printf ".~n"))))

Mencetak '!' untuk setiap cara di mana string dapat dipasangkan. Mencetak '.' pada akhirnya.

Tidak Terkumpul:

(define (f s)
  (let ((sl string-length)                              ; create short names of built-in fns
        (ss substring))
    (if (odd? (sl s))  (printf ".~n")                   ; odd length strings cannot be pairable; end here.
        (begin
          (let loop ((s s))                             ; start testing here
            (if (equal? s "") (printf "!")              ; if no remaining string, it must be pairable
                (for ((i (range 1 (add1 (/(sl s)2)))))  ; ch lengths varying from 1 to half of string length
                  (when (equal? (ss s 0 i)              ; ch if substrings are same
                                (ss s i (* 2 i)))
                    (loop (ss s (* 2 i) (sl s) ))))))   ; if yes, loop to check remaining string.
          (printf ".~n")))))                            ; End of testing.

Pengujian:

(println "Following should be pairable")
(f "bbaabbaa")            ; should produce 2 '!' since 2 ways are possible.
(f "aa")
(f "abaaba")
(f "bbababbb")
(f "aabaaababbbaba")
(f "babababa")                    ; should be pairable in 2 ways.
(f "bbbbbbbbbbbb")                ; should be pairable in many ways.
(f "aaababbabbabbbababbaabaabaababaaba")
(f "aaaabaab")
(println "Following should be unpairable")
; (f "a")
(f "ba")
(f "baab")
(f "abaabaaba")
(f "bbbbbbbbbbbbbbb")
(f "baababbabaaaab")
(f "aaaaabbaaaaa")

Keluaran:

"Following should be pairable"
!!.
!.
!.
!.
!.
!!.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!.
!.
!.
"Following should be unpairable"
.
.
.
.
.
.

Perl, 16 +2 = 18 byte (dengan regex)

Jalankan dengan -nlbendera. -Egratis.

say/^((.+)\2)+$/

Jalankan sebagai:

perl -nlE 'say/^((.+)\2)+$/'

Mengembalikan daftar grup tangkapan (yang benar) jika dapat dipasangkan, string nol jika tidak dapat dipasangkan.

Penjelasan

The -nlbendera akan menjalankan kode dalam satu lingkaran ( -n), menempatkan input (dengan newline yang mengekor dihapus karena -l) ke variabel $_setiap kali, kemudian mengevaluasi kode masing-masing input waktu masuk, sampai program ini dihentikan secara manual. The -Eflag memungkinkan Anda mengevaluasi kode pada baris perintah, dan memungkinkan sayperintah.

say/^((.+)\2)+$/

   /^((.+)\2)+$/  #The regex engine
      (.+)\2      #Find any set of at least one character, followed by itself
     (      )+    #Do this at least one time
   /^         $/  #Make sure that this matches the entire string from start to end
say               #Output the result of the regex

Jika kecocokan ditemukan (misalnya jika string dapat dipasangkan), maka regex mengembalikan daftar kelompok tangkap, yang mengevaluasi ke kebenaran, yang kemudian diteruskan ke say, dan output. Jika tidak ada kecocokan yang ditemukan, maka regex mengembalikan string kosong, yang dievaluasi menjadi falsy, yang kemudian diteruskan kesay , dan output.

Mencicipi:

$ perl -nlE 'say/^((.+)\2)+$/'
aaababbabbabbbababbaabaabaababaaba
baababaababaaba                      #Truthy
baababbabaaaab
                                     #Falsy
bbababbb
bbb                                  #Truthy
aabaaababbbaba
bababa                               #Truthy
abaabaaba
                                     #Falsy

GNU Prolog, 49 46 byte

Mungkin bekerja di varian lain juga, meskipun mereka tidak semuanya mewakili string dengan cara yang sama; Representasi GNU Prolog sangat berguna untuk masalah ini.

Tidak jelas apakah ini dianggap menggunakan regex atau tidak. Itu tidak menggunakan fitur seperti regex, tetapi seluruh semantik bahasa mirip dengan regex.

Versi baru (menggunakan trik rekursi yang terlihat pada beberapa jawaban lain):

s(X):-append(A,B,X),(A=B;A\=X,B\=X,s(A),s(B)).

Versi yang lebih lama:

s(X):-X=[];append(A,B,X),B\=X,append(C,C,A),s(B).

Ini adalah predikat (setara dengan fungsi Prolog) yang disebut s, bukan program lengkap. Gunakan seperti ini:

| ?- s("aa").
true ?
yes
| ?- s("aaababbabbabbbababbaabaabaababaaba").
true ?
yes
| ?- s("baababbabaaaab").
no
| ?- s("bbbbbbbbbbbbbbb").
no

Fitur yang menarik dari solusi yang lebih lama adalah bahwa jika Anda bertanya pada juru bahasa "apakah ada lebih banyak solusi?" melalui penggunaan ;pada true ?prompt (daripada bertanya "apakah ada solusi" melalui menekan kembali pada prompt, seperti yang saya lakukan di atas), ia mengembalikan "true" beberapa kali sama dengan jumlah cara string dapat diekspresikan dalam bentuk yang diberikan (misalnya mengembalikan "true" dua kali dengan s("aaaa")., karena ini dapat diuraikan sebagai (a a)(a a)atau sebagai(aa aa) ).

Program prolog seringkali reversibel (memungkinkan suntuk menghasilkan daftar string dengan properti yang diberikan). Yang lebih tua tidak (itu masuk ke loop tak terbatas), tapi itu karena metode golf yang saya gunakan untuk memastikan bahwa C tidak kosong; jika Anda menulis ulang program untuk menentukan C sebagai nonempty secara eksplisit, itu menghasilkan string dari bentuk "aa", "aabb", "aabbcc", dan sebagainya (Prolog menjadi Prolog, itu tidak menentukan identitas untuk karakter yang membuatnya (hanya spesifikasi yang karakternya sama). Yang lebih baru menghasilkan string dari bentuk "aa", "abab", "abcabc", dan seterusnya; ini adalah loop tak terbatas dalam dirinya sendiri, dan dengan demikian tidak pernah mengenai titik di mana ia akan macet karena gagal mendeteksi string dengan panjang nol.

Brainfuck, 177 byte

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

Diformat:

+[<<<<,]
>>>>
[
  >+
  [
    >+
    [
      [>>]
      <+<[<<]
      >+>-
    ]
    <[>+<-]>
    >>,>>[>>]
    +<<[<+> >-<-]
    <[>+<-]>
    >
    [
      not equal
      ,>[-<<<<]
      <[<<<<]
      >
    ]
    <
    [
      equal
      [<<]
      >
    ]
    >>
  ]
  >>
  [
    mismatch
    [>+>>>]
    >>>[>]
    <<<<
    [
      backtrack
      >+[-<<<,<]
      <
      [
        not done yet
        <<<
        [
          [<<<<]
          >>
        ]
        <
      ]
      >
    ]
    >>
  ]
  <
  [
    match
    [->>>>]
    >>[<]
    <
  ]
  <<
]
<.

Mengharapkan input tanpa baris baru yang tertinggal. Mencetak \x00untuk false dan \x01true.

Cobalah online.

Ini mengimplementasikan pencarian mendalam-pertama. Khususnya: periksa awalan berulang dengan panjang yang meningkat mulai dari sufiks saat ini, kemudian pindah ke sufiks berikutnya jika kecocokan ditemukan, sebaliknya mundur.

Pada awalnya, string dibalik dan sentinel \x01ditempatkan di akhir.

Rekaman itu dibagi menjadi 4-sel node. Tata letak memori suatu simpul adalah:

c h x 0

di mana ckarakter, hadalah bendera untuk apakah karakter berada di paruh pertama dari awalan yang diulang, dan xmerupakan bendera untuk melacak pasangan karakter saat ini sedang dibandingkan. The hbendera tinggal di tempat sementarax bendera membentuk jendela bergerak.

Jika string dapat dipasangkan, pointer mendarat di sebelah sentinel pada akhir loop utama; jika tidak, penunjuk jatuh dari sisi kiri string sambil mundur.

Brachylog , 5 byte

~c~jᵐ

Cobalah online!

Perhatikan bahwa algoritma ini bisa sangat lama, terutama pada kasus falsey, karena memeriksa setiap kemungkinan partisi string input.

Penjelasan

~c     Reversed concatenate: find a list that, when concatenated, results in the input string
       This examines all partitions of the input
  ~jᵐ  Map reversed juxtapose: for each string in that list, is it the result of concatenating
       a string to itself?

Untuk string input seperti "ababcc", ~ccoba partisi yang berbeda sampai tiba ["abab", "cc"], di titik mana ~jberhasil untuk kedua item dari daftar, ᵐoutput ["ab", "c"], dan predikat berhasil.

R , 31 byte

grepl("^((.+)\\2)+$",scan(,""))

Cobalah online!

Berdasarkan jawaban Retina.

R , 129 byte

Dan inilah jawaban asli dan non-regex:

o=(y=utf8ToInt(scan(,"")))<0;for(i in 2*1:(sum(y>0)/2))for(j in 1:(i/2)){w=i:(i-j+1);v=w-j;if(all(y[w]==y[v]))o[c(v,w)]=T};all(o)

Cobalah online!

Lithp , 57 karakter

#S::((? (!= (null) (match S "^((.+)\\2)+$")) true false))

Penggunaan sampel:

% pairable_strings.lithp
(
    (def f #S::((? (!= (null) (match S "^((.+)\\2)+$")) true false)))
    (print (f "aa"))
    (print (f "aabaaababbbaba"))
    (print (f "aaababbabbabbbababbaabaabaababaaba"))
    (print (f "ba"))
)

# ./run.js pairable_strings.lithp
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 3, type: 'Atom', name: 'false' }