Ciąg jest pairable jeżeli można podzielić na subtrings, z których każdy jest ciągiem kolejno powtarzane dwa razy. Na przykład aabaaababbbabamożna go sparować jako:

aaba aaba
b b
ba ba

Biorąc pod uwagę niepuste ciągi a„i b”, wypisz wartość Prawda, jeśli jest parowalna, i wartość Falsey, jeśli nie jest.

Parowanie:

aa
abaaba
bbababbb
aabaaababbbaba
babababa
bbbbbbbbbbbb
aaababbabbabbbababbaabaabaababaaba
aaaabaab

Nie można sparować:

a
ba
baab
abaabaaba
bbbbbbbbbbbbbbb
baababbabaaaab
aaaaabbaaaaa

Zachęcam do wymyślania rozwiązań nieopartych na wyrażeniach regularnych, nawet jeśli w Twoim języku jest już krótsza odpowiedź na wyrażenia regularne. Możesz oznaczyć je jako „bez wyrażenia regularnego”. Przez wyrażenie regularne mam na myśli wbudowany podsystem dopasowania wzorca ciągu.

Tabela liderów:

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 bajtów

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

Zwraca wartość prawda lub fałsz . Przetestuj na Ideone .

Siatkówka , 11 bajtów

^((.+)\2)+$

Wypróbuj wszystkie przypadki testowe. Pierwsze dwa bajty sprawiają, że jest to wieloliniowy.

Całkiem dosłowna interpretacja reguł, oczywiście używa wyrażenia regularnego, tak jak wszystkie programy Retina.

Galaretka , 10 bajtów

ẆŒPẋ€€2F€ċ

Niezupełnie wydajne ... Wypróbuj online!

Jak to działa

ẆŒ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 bajtów (bez wyrażenia regularnego)

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

Podejście brutalnej siły. Wypróbuj na Ideone .

Dzięki BlackCap za -3 bajty.

Wyjaśnienie

Funkcja pomocnika gpobiera listę ciągów znaków i sprawdza, czy składa się z par identycznych ciągów znaków, takich jak ["aa","aa","bba","bba","ab","ab"]. (Anonimowa) funkcja główna dzieli ciąg na wszystkie możliwe sposoby i sprawdza, czy co najmniej jedno dzielenie daje listę, która gakceptuje.

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 bajtów

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

Mam nadzieję, że to prawda. Działa dość wolno i andnie wygląda optymalnie.

Galaretka , 12 bajtów

ŒṖµœs€2ZEµ€S

Dwa bajty dłuższe niż moja inna odpowiedź , ale to podejście jest znacznie bardziej wydajne i obsługuje wszystkie przypadki testowe oprócz jednego.

Wypróbuj online!

Jak to działa

ŒṖµœ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 - Bez Regex - 13 12 bajtów

Sprawdza, czy którakolwiek z partycji składa się ze wszystkich ciągów, które są sobie równe po podzieleniu na dwie części.

sm.AqMcL2d./

Pakiet testowy .

Brachylog , 14 bajtów (bez wyrażenia regularnego)

lye~l:1j@2zcc?

Wypróbuj online!

Jest to zbyt wolne w przypadku niektórych przypadków testowych

Wyjaśnienie

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), bez wyrażenia regularnego, 75 74 bajtów

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

W 1przeciwnym razie zwraca do parowania 0. Edycja: Zapisano 1 bajt dzięki @ edc65.

Python, 58 bajtów

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

Jest to oparte na rekurencyjnej metodzie Dennisa . Stąd bierze się również logiczna sztuczka negacji.

Nowym pomysłem jest powtarzanie się w partycjach (p,s)oryginalnego łańcucha, zaczynając od ('',s)i wielokrotnie przesuwając pierwszą postać, saby była ostatnią postacią p. Umożliwia to bezpośrednie odwoływanie się do części bez przecinania sznurka. Ponieważ jednak partycja zaczyna się od ppustego, musimy uważać, aby uniknąć nieskończonych pętli f(s)wywoływania f(s).

JavaScript (ES6), 24 bajty

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

Prawdopodobnie nie jest krótszy niż ten.

PHP, 40 bajtów

wypisuje 0 dla false i 1 dla true

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

Python, 66 64 bajtów

Dzięki @Zgarb za -1 bajt!

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

Zwraca Truelub False.

Wypróbuj online!

Każda pomoc w golfa będzie mile widziana.

Rakieta 230 bajtów

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

Drukuje „!” dla każdego sposobu, w jaki ciąg jest parowany. Drukuje „.” na końcu.

Nie golfowany:

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

Testowanie:

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

Wydajność:

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

Perl, 16 +2 = 18 bajtów (z wyrażeniem regularnym)

Uruchom z -nlflagami. -Ejest wolny.

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

Uruchom jako:

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

Zwraca listę grup przechwytywania (prawda), jeśli można je sparować, łańcuch zerowy, jeśli nie można sparować.

Wyjaśnienie

Te -nlflagi będą uruchamiać kod w pętli ( -n), umieszczenie wejściowe (z tylną przełamane usunięte ze względu -l) w zmiennej $_za każdym razem, a następnie oceny kodowe wejście czas wprowadzony do momentu, gdy program jest ręcznie zakończone. -EFlaga pozwala kod w wierszu poleceń oceniać i umożliwia saypolecenie.

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

Jeśli zostanie znalezione dopasowanie (np. Jeśli ciąg znaków można sparować), wyrażenie regularne zwraca listę grup przechwytywania, która zwraca wartość true, która jest następnie przekazywana sayi generowana. Jeśli nie zostanie znalezione dopasowanie, wyrażenie regularne zwraca pusty ciąg znaków, który przekształca się w fałsz, który jest następnie przekazywany sayi generowany.

Próba:

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

GNU Prolog, 49 46 bajtów

Prawdopodobnie działa również w innych wariantach, chociaż nie wszystkie reprezentują ciągi w ten sam sposób; Reprezentacja GNU Prolog jest przydatna w przypadku tego problemu.

Nie jest jasne, czy liczy się to jako użycie wyrażenia regularnego, czy nie. Nie używa żadnej funkcji podobnej do wyrażenia regularnego, ale cała semantyka języka jest podobna do wyrażeń regularnych.

Nowa wersja (wykorzystuje sztuczkę rekurencyjną widoczną w innych odpowiedziach):

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

Starsza wersja:

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

Jest to wywołany predykat (odpowiednik funkcji Prologa) s, a nie pełny program. Użyj tego w ten sposób:

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

Ciekawą cechą starszego rozwiązania jest to, że jeśli zapytasz tłumacza „czy jest więcej rozwiązań?” poprzez korzystanie z ;Pod true ?szybka (zamiast pytać „czy istnieje jakieś rozwiązanie” poprzez naciśnięcie powrót w wierszu, jak ja powyżej), to zwraca „true” kilka razy równa liczbie różnych sposobów ciąg może być wyrażony w podanej formie (np. zwraca dwa razy „prawda” s("aaaa")., ponieważ można to parsować jako (a a)(a a)lub jako (aa aa)).

Programy prolog często są odwracalne (pozwalający sna generowanie listy ciągów z danej nieruchomości). Starsza nie jest (przechodzi w nieskończoną pętlę), ale to z powodu metody golfowej, której użyłem, aby upewnić się, że C nie jest puste; jeśli przepiszesz program, aby jawnie podać C jako niepuste, wygeneruje ciągi znaków w postaci „aa”, „aabb”, „aabbcc” itd. (Prolog jest Prologem, nie określa tożsamości tworzących je znaków w górę, tylko specyfikacja, które znaki są takie same). Nowsze generuje ciągi znaków w postaci „aa”, „abab”, „abcabc” i tak dalej; jest to nieskończona pętla sama w sobie, a zatem nigdy nie osiągnie punktu, w którym utknie z powodu niewykrycia ciągu o zerowej długości.

Brainfuck, 177 bajtów

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

Sformatowany:

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

Oczekuje wprowadzania bez końcowego znaku nowej linii. Drukuje \x00jako fałszywe i \x01prawdziwe.

Wypróbuj online.

To implementuje wyszukiwanie w pierwszej kolejności. W szczególności: sprawdź powtarzające się prefiksy o większej długości, zaczynając od bieżącego sufiksu, a następnie przejdź do następnego sufiksu, jeśli znaleziono dopasowanie, w przeciwnym razie cofnij się.

Na początku łańcuch jest odwracany, a \x01na końcu umieszczany jest wartownik .

Taśma jest podzielona na 4-komórkowe węzły. Układ pamięci węzła to:

c h x 0

gdzie cjest znakiem, hoznacza flagę określającą, czy znak znajduje się w pierwszej połowie powtarzanego prefiksu, i xflagę służącą do śledzenia bieżącej pary porównywanych znaków. Te hflagi pozostać w miejscu, podczas gdy xflagi tworząc okno poruszający.

Jeśli łańcuch można sparować, wskaźnik wyląduje obok wartownika na końcu głównej pętli; w przeciwnym razie wskaźnik spadnie z lewej strony łańcucha podczas cofania.

Brachylog , 5 bajtów

~c~jᵐ

Wypróbuj online!

Zauważ, że ten algorytm może zająć bardzo dużo czasu, szczególnie w przypadkach falsey, ponieważ sprawdza każdą możliwą partycję ciągu wejściowego.

Wyjaśnienie

~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?

W przypadku ciągu wejściowego, takiego jak "ababcc", ~cpróbuje różnych partycji, aż dojdzie do tego ["abab", "cc"], w którym momencie ~joba elementy listy, ᵐwyniki ["ab", "c"]i predykat się powiodą.

R , 31 bajtów

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

Wypróbuj online!

Na podstawie odpowiedzi Retina.

R , 129 bajtów

A oto oryginalna odpowiedź, która nie jest wyrażeniem regularnym:

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)

Wypróbuj online!

Lithp , 57 znaków

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

Przykładowe użycie:

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