# How compatible are my strings?

## Introduction

Consider two strings A and B of the same length L, and an integer K ≥ 0. For the purposes of this challenge, we say that the strings are K-compatible, if there exists a string C of length K such that A is a contiguous substring of the concatenation BCB. Note that A is a substring of BAB, so A and B are always L-compatible (but may also be K-compatible for some other K < L).

## Input

Your inputs are two strings of the same positive length, consisting of upper- and lowercase ASCII letters.

## Output

Your output shall be the lowest non-negative integer K such that the inputs are K-compatible.

## Example

Consider the inputs

A = HHHHHH
B = HHttHH


They are not 0-compatible, because A is not a substring of HHttHHHHttHH. They are also not 1-compatible, because A is not a substring of HHttHH#HHttHH no matter which letter is placed on the #. However, A is a substring of HHttHHHHHHttHH, where C is the two-letter string HH. Thus the inputs are 2-compatible, and the correct output is 2.

## Rules and scoring

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

## Test cases

The compatibility condition is symmetric, so swapping the two inputs should not change the output.

E G -> 1
E E -> 0
aB Bc -> 1
YY tY -> 1
abcd bcda -> 0
abcXd bxcda -> 4
Hello Hello -> 0
Hello olHel -> 1
aBaXYa aXYaBa -> 1
aXYaBa aBaXYa -> 1
HHHHHH HHttHH -> 2
abcdab cdabcd -> 2
XRRXXXXR XRXXRXXR -> 4
evveeetev tetevevev -> 7
vzzvzJvJJz vJJvzJJvJz -> 10
JJfcfJJcfJfb JcfJfbbJJJfJ -> 5
GhhaaHHbbhGGH HHaaHHbbGGGhh -> 9
OyDGqyDGDOGOGyG yDGqOGqDyyyyOyD -> 12
ffKKBBpGfGKpfGpbKb fGpbKbpBBBffbbbffK -> 9
UZuPPZuPdVdtuDdDiuddUPtUidtVVV dtUPtUidtVVVtDZbZZPuiUZuPPZuPd -> 21


Here's a Stack Snippet to generate a leaderboard and list of winners by language. To make sure your answer shows up, start it with a header of the form

## Language, N bytes


You can keep old scores in the header by using the strikethrough tags: <s>57</s> will appear as 57.

/* Configuration */

var QUESTION_ID = 78736; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 32014; // This should be the user ID of the challenge author.

/* App */

return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(a) {
});
comment_page = 1;
}
});
}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
});
else process();
}
});
}

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(-?\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

function getAuthorName(a) {
return a.owner.display_name;
}

function process() {
var valid = [];

var body = a.body;
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});

var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
});

});

valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});

var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;

.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)

var lang = a.language;
if (! /<a/.test(lang)) lang = '<i>' + lang + '</i>';
lang = jQuery(lang).text().toLowerCase();

languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link, uniq: lang};
});

var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);

langs.sort(function (a, b) {
if (a.uniq > b.uniq) return 1;
if (a.uniq < b.uniq) return -1;
return 0;
});

for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
language = jQuery(language);
jQuery("#languages").append(language);
}

}
body { text-align: left !important}

width: 290px;
float: left;
}

#language-list {
width: 290px;
float: left;
}

font-weight: bold;
}

table td {
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>

</tbody>
</table>
</div>
<div id="language-list">
<h2>Winners by Language</h2>
<table class="language-list">
<tr><td>Language</td><td>User</td><td>Score</td></tr>
<tbody id="languages">

</tbody>
</table>
</div>
<table style="display: none">
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
</tbody>
</table>

# Pyth, 16

lhf}QjT,vzvz+k.:


Find the shortest substring of A that when inserted between two copies of B results in a string that contains A.

This could be two bytes shorter if the second line didn't have quotes, but that feels weird?

Test Suite

# Python 3, 155168 157 bytes

Total is the length of A. Compare the beginning of A to the end of B and subtract that from total. Compare the beginning of B to the end of A and subtract that from total. Return the absolute value of total unless total is equal to the length, in which case return 0.

def f(A,B):
T=L=len(A)
C=D=1
for i in range(L,0,-1):
if A[:i]==B[-i:]and C:
T,C=T-i,0
if A[-i:]==B[:i]and D:
T,D=T-i,0
return (0,abs(T))[T!=-L]


Edit: Handle the f("abcdab","cdabcd")==2 case

• Unfortunately this doesn't work for f("abcdab", "cdabcd") which should be 2. – Neil Apr 27 '16 at 19:58
• @Neil Good catch. I'll add that to the test cases. – Zgarb Apr 27 '16 at 21:17
• – F. George Feb 11 '17 at 23:01
• @mEQ5aNLrK3lqs3kfSa5HbvsTWe0nIu I was looking at the image and thinking 'This is a nifty debugger idea to use emojis, but I dont see a bug...'. I think that add-on would wreak havoc on this site. – NonlinearFruit Feb 12 '17 at 2:28

## Retina, 49 bytes

.*?(?<=^(?=(.*)(?<4-3>.)*(.*) \2.*\1$)(.)*).+$#4


Try it online! (Slightly modified to run all tests at once.)

The trick is that we need to backtrack over the part of A that we don't find in B, and so far I haven't found a way to do this without rather annoying lookarounds and balancing groups.

# Jolf, 40 Bytes

Wά)Ζ0W<ζli)? h++i]Iζ+ζniIoά0nΖhζ}onhn}wn


Try it!

I'm quite new to Jolf, learned a lot while figuring this out. Seems a bit awkward, still could probably could be golfed down further. Even knocked off 2 bytes while writing this explanation.

Explanation:

  Wά)                                      While ά (initialized to 16)
Ζ0                                    Set ζ to 0
W<ζli)                              While ζ < length(A)
? h++i]Iζ+ζniIoά0n            Set ά to 0 if (A + a substring from B of length n + A) contains B
Ζhζ         Increment ζ
}onhn    Increment n (initialize to 0
}wn Decrement n and print

• I haven't tried in earnest, and this may be an optimal solution, but I suggest trying to map over ranges. (s0zli will give you an array [0 ... length i] if you wish to try this approach.) – Conor O'Brien Apr 28 '16 at 22:30
• @Cᴏɴᴏʀ O'Bʀɪᴇɴ Hmm, I'll give that a look... also is there an if command that I jmissed while looking through the documentation/source or is the only option ? with an irrelevant third argument? – swells Apr 29 '16 at 11:23
• ? is the closest to an if there is in Jolf. It's like a ternary if. ?ABCs returns B if a is true, and C otherwise. – Conor O'Brien Apr 29 '16 at 11:27

# 05AB1E, 20 bytes

Code:

õ)²Œ«v¹y¹««²åiyg}})ß


Uses CP-1252 encoding. Try it online!.

## JavaScript (ES6), 110 bytes

(a,b)=>{for(i=0;;i++)for(j=i;j<=a.length;j++)if(b.startsWith(a.slice(j))&&b.endsWith(a.slice(0,j-i)))return i}


Works by slicing ever longer pieces out of the middle of a until they match the two ends of b. The loop is not infinite as it will stop on or before i == a.length`.