10
\$\begingroup\$

Write a program or function that, given two ASCII strings A and B, will produce strings A' and B' where the common substrings are reversed in their place. The process for finding A' is as follows:

  1. A' is initially empty.
  2. If the first character of A is in B, find the longest prefix of A which is a substring of B. Remove this prefix from A and add its reversal to A'.
  3. Otherwise, remove this first character from A and add it to A'.
  4. Repeat steps 2-3 until A is empty.

Finding B' is done similarly.

Example

Let's consider the strings A = "abc bab" and B = "abdabc". For A', this is what happens:

  • A = "abc bab": The first character "a" is in B and the longest prefix of A found in B is "abc". We remove this prefix from A and add its reversal "cba" to A'.
  • A = " bab": The first character " " is not in B, so we remove this character from A and add it to A'.
  • A = "bab": The first character "b" is in B and the longest prefix of A found in B is "b". We remove this prefix from A and add its reversal (which is still "b") to A'.
  • A = "ab": The first character "a" is in B and the longest prefix of A found in B is "ab". We remove this prefix from A and add its reversal "ba" to A'.
  • A = "": A is empty, so we stop.

Thus we get A' = "cba" + " " + "b" + "ba" = "cba bba". For B', the process is similar:

B = "abdabc"  ->  "a" in A, remove prefix "ab"
B = "dabc"    ->  "d" not in A, remove "d"
B = "abc"     ->  "a" in A, remove prefix "abc"

Thus we get B' = "ba" + "d" + "cba" = "badcba".

Finally, we return the two strings, i.e.

(A', B') = ("cba bba", "badcba")

Test cases

"abc bab", "abdabc" -> "cba bba", "badcba"
"abcde", "abcd bcde" -> "dcbae", "dcba edcb"
"hello test", "test banana" -> "hello tset", "tset banana"
"birds flying high", "whistling high nerds" -> "bisdr flyhgih gni", "wihstlhgih gni nesdr"

Shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Do we presume all input is lowercase ASCII? Is the exact output expected to be akin to "cba bba", "badcba" including quotes and comma? \$\endgroup\$ – AdmBorkBork Aug 26 '15 at 20:23
  • \$\begingroup\$ @TimmyD The exact input/output format is your choice. You may not presume the input is lowercase ASCII - it could be any printable ASCII. \$\endgroup\$ – orlp Aug 26 '15 at 20:51
  • \$\begingroup\$ Is the empty string a legal input? \$\endgroup\$ – MtnViewMark Aug 27 '15 at 5:25
  • \$\begingroup\$ @MtnViewMark Yes. \$\endgroup\$ – orlp Aug 27 '15 at 8:02
1
\$\begingroup\$

Pyth, 29 bytes

M&G+_Je|f}TH._GhGg.-GJHgzQgQz

Test Harness.

Input format is:

abc bab
"abdabc"

Output is:

cba bba
badcba
\$\endgroup\$
2
\$\begingroup\$

Haskell, 120 111 bytes

import Data.List
a&b=(a#b,b#a)
[]#_=[]
(a:y)#b=[a]%y where p%(i:w)|reverse(i:p)`isInfixOf`b=(i:p)%w;p%x=p++x#b

Test runs:

λ: "abc bab"&"abdabc"
("cba bba","badcba")

λ: "abcde"&"abcd bcde"
("dcbae","dcba edcb")

λ: "hello test"&"test banana"
("hello tset","tset banana")

λ: "birds flying high"&"whistling high nerds"
("bisdr flyhgih gni","wihstlhgih gni nesdr")
\$\endgroup\$
1
\$\begingroup\$

SWI-Prolog, 312 bytes

a(A,B,X,Y):-b(A,B,"",X),b(B,A,"",Y).
b(A,B,R,Z):-A="",R=Z;sub_string(A,0,1,_,C),(sub_string(B,_,1,_,C),(string_length(A,J),I is J-1,between(0,I,K),L is J-K,sub_string(A,0,L,_,S),sub_string(B,_,L,_,S),string_codes(S,E),reverse(E,F),string_codes(Y,F));S=C,Y=C),string_concat(S,V,A),string_concat(R,Y,X),b(V,B,X,Z).

Example: a("birds flying high","whistling high nerds",X,Y). outputs

X = "bisdr flyhgih gni",
Y = "wihstlhgih gni nesdr" .

A way, way too long solution that goes too show how verbose Prolog is when dealing with strings. It might be possible to shorten this thing using codes arrays (`birds flying high`) instead of strings ("birds flying high").

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

Python 2.7, 169 156 152 141 Bytes

m=lambda A,B:(b(A,B),b(B,A))
def b(A,B,C=''):
 while A:j=next((j for j in range(len(A),0,-1)if A[:j]in B),1);C+=A[:j][::-1];A=A[j:]
 return C

The function m takes the 2 strings as input.It calls the b function twice which does the actual processing according to the specs.
Demo here.
Testing it -

l=[("abc bab", "abdabc"),
("abcde", "abcd bcde"),
("hello test", "test banana"),
("birds flying high", "whistling high nerds")]
for e in l:
    print m(*e)

OUTPUTS:

('cba bba', 'badcba')
('dcbae', 'dcba edcb')
('hello tset', 'tset banana')
('bisdr flyhgih gni', 'wihstlhgih gni nesdr')

PS: Thanks to orlp for the solution using next()

\$\endgroup\$
  • \$\begingroup\$ m=lambda A,B:(b(A,B),b(B,A)) \$\endgroup\$ – orlp Aug 26 '15 at 21:02
  • \$\begingroup\$ Also you can replace while len(A)>0 with just while A. Similarly if len(p)>0 becomes if p. \$\endgroup\$ – orlp Aug 26 '15 at 21:03
  • \$\begingroup\$ if len(p) can also be if p. (Already said above, but you missed it.) \$\endgroup\$ – mbomb007 Aug 26 '15 at 21:10
  • \$\begingroup\$ @mbomb007 Didn't read it properly. Just replaced len(p)>0 to len(p). Thanks for that :) \$\endgroup\$ – Kamehameha Aug 26 '15 at 21:14
  • \$\begingroup\$ Even shorter: while A:j=next((j for j in range(len(A),0,-1)if A[:j]in B),1);C+=A[:j][::-1];A=A[j:]. \$\endgroup\$ – orlp Aug 26 '15 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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