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

[Try it online.](http://brainfuck.tryitonline.net/#code=K1s8PDw8LF0-Pj4-Wz4rWz4rW1s-Pl08KzxbPDxdPis-LV08Wz4rPC1dPj4-LD4-Wz4-XSs8PFs8Kz4-LTwtXTxbPis8LV0-PlssPlstPDw8PF08Wzw8PDxdPl08W1s8PF0-XT4-XT4-W1s-Kz4-Pl0-Pj5bPl08PDw8Wz4rWy08PDwsPF08Wzw8PFtbPDw8PF0-Pl08XT5dPj5dPFtbLT4-Pj5dPj5bPF08XTw8XTwu&input=YmFhYmFhYWE)

This implements depth-first search. In particular: check for repeated prefixes of increasing length starting from the current suffix, then move to the next suffix 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.