How compatible are my strings?

Question

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

Leaderboard

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 ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 32014; // This should be the user ID of the challenge author.
/* App */
var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;
function answersUrl(index) {
 return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}
function commentUrl(index, answers) {
 return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}
function getAnswers() {
 jQuery.ajax({
 url: answersUrl(answer_page++),
 method: "get",
 dataType: "jsonp",
 crossDomain: true,
 success: function (data) {
 answers.push.apply(answers, data.items);
 answers_hash = [];
 answer_ids = [];
 data.items.forEach(function(a) {
 a.comments = [];
 var id = +a.share_link.match(/\d+/);
 answer_ids.push(id);
 answers_hash[id] = a;
 });
 if (!data.has_more) more_answers = false;
 comment_page = 1;
 getComments();
 }
 });
}
function getComments() {
 jQuery.ajax({
 url: commentUrl(comment_page++, answer_ids),
 method: "get",
 dataType: "jsonp",
 crossDomain: true,
 success: function (data) {
 data.items.forEach(function(c) {
 if (c.owner.user_id === OVERRIDE_USER)
 answers_hash[c.post_id].comments.push(c);
 });
 if (data.has_more) getComments();
 else if (more_answers) getAnswers();
 else process();
 }
 }); 
}
getAnswers();
var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(-?\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;
var OVERRIDE_REG = /^Override\s*header:\s*/i;
function getAuthorName(a) {
 return a.owner.display_name;
}
function process() {
 var valid = [];
 
 answers.forEach(function(a) {
 var body = a.body;
 a.comments.forEach(function(c) {
 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],
 link: a.share_link,
 });
 
 });
 
 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;
 
 var answer = jQuery("#answer-template").html();
 answer = answer.replace("{{PLACE}}", lastPlace + ".")
 .replace("{{NAME}}", a.user)
 .replace("{{LANGUAGE}}", a.language)
 .replace("{{SIZE}}", a.size)
 .replace("{{LINK}}", a.link);
 answer = jQuery(answer);
 jQuery("#answers").append(answer);
 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)
 .replace("{{LINK}}", lang.link);
 language = jQuery(language);
 jQuery("#languages").append(language);
 }
}

body { text-align: left !important}
#answer-list {
 padding: 10px;
 width: 290px;
 float: left;
}
#language-list {
 padding: 10px;
 width: 290px;
 float: left;
}
table thead {
 font-weight: bold;
}
table td {
 padding: 5px;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/Sites/codegolf/all.css?v=617d0685f6f3">
<div id="answer-list">
 <h2>Leaderboard</h2>
 <table class="answer-list">
 <thead>
 <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
 </thead>
 <tbody id="answers">
 </tbody>
 </table>
</div>
<div id="language-list">
 <h2>Winners by Language</h2>
 <table class="language-list">
 <thead>
 <tr><td>Language</td><td>User</td><td>Score</td></tr>
 </thead>
 <tbody id="languages">
 </tbody>
 </table>
</div>
<table style="display: none">
 <tbody id="answer-template">
 <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr>
 </tbody>
</table>
<table style="display: none">
 <tbody id="language-template">
 <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr>
 </tbody>
</table>

Answer 1

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

Answer 2

Python 3, (削除) 155 (削除ここまで) (削除) 168 (削除ここまで) 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

• Neil: Unfortunately this doesn't work for f("abcdab", "cdabcd") which should be 2.
• Zgarb: @Neil Good catch. I'll add that to the test cases.
• F. George: That was unexpected. (Global Twitch Emotes)
• NonlinearFruit: @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.

Answer 3

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.

Answer 4

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

• Conor O'Brien: 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.)
• swells: @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?
• Conor O'Brien: ? 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.

Answer 5

05AB1E, 20 bytes

Code:

õ)2Œ«v1y1««2åiyg}})ß

Uses CP-1252 encoding. Try it online!.

Answer 6

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.