12
\$\begingroup\$

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>

Improve this question
\$\endgroup\$
0

6 Answers 6

Reset to default
8
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Unfortunately this doesn't work for f("abcdab", "cdabcd") which should be 2. \$\endgroup\$ Commented Apr 27, 2016 at 19:58
  • \$\begingroup\$ @Neil Good catch. I'll add that to the test cases. \$\endgroup\$ Commented Apr 27, 2016 at 21:17
  • 1
    \$\begingroup\$ That was unexpected. (Global Twitch Emotes) \$\endgroup\$ Commented Feb 11, 2017 at 23:01
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Feb 12, 2017 at 2:28
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ 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.) \$\endgroup\$ Commented Apr 28, 2016 at 22:30
  • \$\begingroup\$ @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? \$\endgroup\$ Commented Apr 29, 2016 at 11:23
  • \$\begingroup\$ ? 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. \$\endgroup\$ Commented Apr 29, 2016 at 11:27
2
\$\begingroup\$

05AB1E, 20 bytes

Code:

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

Uses CP-1252 encoding. Try it online!.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.