Brainfuck, 177 bytes
+[<<<<,]>>>>[>+[>+[[>>]<+<[<<]>+>-]<[>+<-]>>>,>>[>>]+<<[<+>>-<-]<[>+<-]>>[,>[-<<
<<]<[<<<<]>]<[[<<]>]>>]>>[[>+>>>]>>>[>]<<<<[>+[-<<<,<]<[<<<[[<<<<]>>]<]>]>>]<[[-
>>>>]>>[<]<]<<]<.
Formatted:
+[<<<<,]
>>>>
[
>+
[
>+
[
[>>]
<+<[<<]
>+>-
]
<[>+<-]>
>>,>>[>>]
+<<[<+> >-<-]
<[>+<-]>
>
[
not equal
,>[-<<<<]
<[<<<<]
>
]
<
[
equal
[<<]
>
]
>>
]
>>
[
mismatch
[>+>>>]
>>>[>]
<<<<
[
backtrack
>+[-<<<,<]
<
[
not done yet
<<<
[
[<<<<]
>>
]
<
]
>
]
>>
]
<
[
match
[->>>>]
>>[<]
<
]
<<
]
<.
Expects input without a trailing newline. Prints \x00
for false and \x01
for true.
This implements depth-first search. In particular: check for repeated prefixes of increasing length starting from the current postfixsuffix, then move to the next postfixsuffix if a match is found, otherwise backtrack.
At the beginning, the string is reversed and a sentinel \x01
is placed at the end.
The tape is divided into 4-cell nodes. The memory layout of a node is:
c h x 0
where c
is the character, h
is a flag for whether the character is in the first half of a repeated prefix, and x
is a flag to keep track of the current pair of characters being compared. The h
flags stay in place while the x
flags form a moving window.
If the string is pairable, the pointer lands next to the sentinel at the end of the main loop; otherwise, the pointer falls off the left side of the string while backtracking.