Problem 95. Given two strings, find the maximum overlap

Created by Cody Team

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given two strings s1 and s2, create a new string s3 which is as short as possible and contains both strings.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ s1 = [1 2 3 4 5]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>and</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ s2 = [5 4 3 2]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>then</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ s3 = [1 2 3 4 5 4 3 2]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>There is guaranteed to be one best solution.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

1571 Solutions
424 Solvers

Last Solution submitted on Oct 21, 2020

Last 200 Solutions

Problem Comments

9 Comments

9 Comments

Show 6 older comments

David Young on 8 Feb 2012

This would be improved by a richer test set to avoid solutions based on simple lookup of the test cases.

I think we can assume the entries are all positive integers, but it would be good if that was stated in the problem specification.

Aurelien Queffurust on 29 Jun 2012

Definetely agree. Adding more tests in the test suite and rescoring the solutions will elmiminate solution under a score of 92

Richard Zapor on 6 Jul 2012

My 33 is a terrible solution. Please add more test cases.
Tim's 80 is very good and my 83 is also valid. Addition of a common random value at an end overlap will eliminate chicanery. v=randi(100) [1 2 3 v] [v 4 5].

Richard Zapor on 6 Jul 2012

Created legitimate size 72.

Ned Gulley on 6 Jul 2012

Added a few more tests. Thanks for the comments!

Luigi Sanguigno on 28 Oct 2012

s1 = [3 1 4 1 5 9 2 6 5 3 5];
s2 = [9 2 6 5];
s3_correct = [3 1 4 1 5 9 2 6 5 3 5]; maybe is not correct ;-)

Michael Eldredge on 13 Feb 2018

Problems 1 and 2 have alternate solutions:

1) [5 4 3 1 2 3 4 5]
2) [1 0 1 7 7 7 6 0 1]

Sanzhar Askaruly on 21 Aug 2019

Did I just solved this myself? Toughest for me so far. Thanks!!!

Bryan Lambo on 8 Jan 2020

This did not make me sleep. Most difficult so far, took me some few hours lol.

Solution Comments

Solution 1182647

2 Comments

2 Comments

han gao on 1 Jan 2018

can't understand

Alex on 19 Jun 2020

Try this with: [ 1 2 3], [3 1 2]
Finds: [1 2 3 1 2]
Should find: [3 1 2 3]

Solution 49798

1 Comment

1 Comment

shen on 15 Dec 2013

hello, have you ever tried s1 = [ 1 2 3 ], s2= [1 2]?

Solution 33563

2 Comments

2 Comments

blaat on 11 Feb 2012

Nice :) I was trying to think of clever ways to use convolution, but didn't manage. This should be the leading solution instead of the lookup based on the test cases..

Aurelien Queffurust on 11 Jul 2012

well commneted

Solution 9598

1 Comment

1 Comment

Peter Wittenberg on 25 May 2012

Come on. Put in a general solution rather than gaming the solution set.

Problem Recent Solvers424

Problem Tags

matlab

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 95. Given two strings, find the maximum overlap

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers424

Suggested Problems

More from this Author95

Problem Tags

Community Treasure Hunt

Problem 95. Given two strings, find the maximum overlap

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers424

Suggested Problems

More from this Author95

Problem Tags

Community Treasure Hunt

Players