7
\$\begingroup\$

The task

In this challenge, your task is to determine whether some string occurs as a substring of a given string both surrounded by another string and reversed.

Your input is a non-empty string S of lowercase ASCII letters. If there exist non-empty strings A and B such that the concatenation ABA and the reversal rev(B) are both contiguous substrings of S, then your output shall be a truthy value. Otherwise, your output shall be a falsy value. The two substrings may occur in any order, and they can even overlap. However, it can be shown that in all truthy cases, you can either find non-overlapping substrings or a solution where B is a palindrome.

Example

Consider the input string S = zyxuxyzxuyx. We choose A = xu and B = xyz, and then we can find the following substrings:

S      = zyxuxyzxuyx
ABA    =   xuxyzxu
rev(B) = zyx

The choice A = x and B = u would also be valid. The correct output in this case is truthy.

Rules and scoring

You can write a full program or a function. Standard loopholes are disallowed. The lowest byte count wins.

Test cases

Truthy

sds
aaxyxaa
aaxyaaayx
hgygjgyygj
zyxuxyzxuyx
cgagciicgxcciac
iecgiieagcigaci
oilonnsilasionloiaammialn
abbccdeeaabccddbaacdbbaccdbaaeeccddb

Falsy

a
aaxyaa
jjygjhhyghj
abcaabbccaabca
egaacxiagxcaigx
lnsiiosilnmosaioollnoailm
cabbccabdcaddccabbddcaabbdcaddccaadcabbccaabbcadcc

Fun fact

One can construct arbitrarily long falsy strings using four distinct letters, but not using three letters. The fourth falsy test case is the longest possible.

\$\endgroup\$
3
  • \$\begingroup\$ I think abcaabbccaabcaa is still falsy with three distinct letters. \$\endgroup\$ Jun 20, 2017 at 12:06
  • \$\begingroup\$ @EriktheOutgolfer Choose A = caa and B = b, and look at the end of the string. \$\endgroup\$
    – Zgarb
    Jun 20, 2017 at 12:09
  • \$\begingroup\$ Oh...yeah I don't have much time to check while golfing... \$\endgroup\$ Jun 20, 2017 at 12:13

5 Answers 5

5
\$\begingroup\$

Brachylog, 13 bytes

s↔B&sA,B,A~s?

Try it online!

How it works

s↔B&sA,B,A~s?
s              the input has substring temp
 ↔B            temp reversed is B
   &           and the input
    sA         has substring A
      ,B,A     A,B,A
          ~s?  is a substring of input
\$\endgroup\$
1
  • \$\begingroup\$ Ah right. I was wondering how you ensured that A was nonempty, but the s immediately after the & takes care of that. \$\endgroup\$
    – user62131
    Jun 20, 2017 at 12:52
3
\$\begingroup\$

Retina, 40 bytes

(.+)(.)+\1.*(?<=(?=(?<-2>\2)+(?(2)A)).*)

Try it online!

Big thanks to Martin for fixing a bug with the expression.

Matches ABA then the rest of the string. While doing this, it pushes B's characters onto a stack. Looks backwards over the whole string to find B in reverse order, by traversing forward again and popping characters off of the stack as it matches them ((?<-2>\2)+). Then it makes sure the stack is empty by trying to match a capital letter, which won't be in the input, if the stack still is full.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 53 bytes

->s{s.scan(/(?=(.+)(.+)\1)/).any?{|a,b|s[b.reverse]}}

Fairly straightforward. The only real trick is the positive lookahead (?=...) in the regex, which is used to find all matches and not just non-overlapping ones.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

PHP, 95 bytes

<?=($p=preg_match_all)('#(?=(.+)(.+)\1)#',$argn,$t)&&$p(strrev("#".join("|",$t[2])."#"),$argn);

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Jelly, 21 bytes

Ḣ⁼Ṫȧ
ẆŒṖ€ẎÇÐfẎ€QUẇ€⁸Ṁ

Try it online!

Very inefficient.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.