Join by overlap

Code Golf

string add tag

petStorm

Given a list of strings, output these strings joined by their largest overlapping parts. Your output has to be *optimal*. Strings *have* to be joined in the order given.
## Procedure
Suppose you have a list of strings:
```
["abc","bcd","rfh","hal"]
```
You connect them by their longest common substring:
```
abc
 bcd
    rfh
      hal
=========
abcdrfhal
```
Therefore the expected output is `abcdrfhal`.
## Further specification
You cannot join two strings if their substring can be found in the middle. For example:
```
["aXc","bXd"]
```
If you try to match them by the middle substring:
```
aXc
bXd
```
You would realize that the other overlapping characters are not equal to each other. That is, `a` is not equal to `b`, and `c` is not equal to `d`. In that case you simply append the string in the join:
```
aXc
   bXd
======
aXcbXd
```
---
Likewise, if either of these strings contain each other, but isn't equal to the other string, you should simply append the string. E.g.
```
["abcd","bc"]
```
would give
```
abcd
    bc
======
abcdbc
```

---
Substrings can overlap past each other. E.g.
```
["abc","bcd","cde"]
```
would result in the following join:
```
abc
 bcd
  cde
=====
abcde
```
which would evidently make the output `abcde`.

---
Strings have to overlap as much as possible. That means, in this example:
```
["abcbc","bcbcd"]
```
This is not okay (even if they do overlap):
```
abcbc
   bcbcd
========
abcbcbcd
```
Instead, this should be done:
```
abcbc
 bcbcd
======
abcbcd
```
---
The join is consecutive based on the consecutive inputs. For example:
```
abcde
  cde
     abcde
==========
abcdeabcde
```
## Test cases
A program is worth a thousand words. [Here](https://tio.run/##jVHBboQgEL3zFRNOkLCb3WsTv6KXvQJinES0gjab/rwdlIjNmrYcRnnz5s2bAYdlaebewlsF3k3tUAutwCgGdGLn9TNlbuu1GYJABXcFGiJ@OfDYC7P@yq0gHWyEBvd879A6sREvKKGqwOzwTeGhorSqAHdUshJJMxPISykMbppDT26uVzAH@o6XftnIqiJX/iF5hm4Yk4zF2fzYTm4RE6hBT3lIuMB9a68p@@lCdC/9Zdqh07alPR6miDR4eoS0XbrJ11EIZXIhJ6LDOAmujeWKG1tTDE1LsdUdlxI@AvZT17NC9d5TehzHRA2B5@2eUUk16ybl/SFOqQ9DRPsotN9Ud6@2dn8YqFfuv1RJSwHPn@1eqMs3) 's a reference implementation that I use to check the test cases.
```
["abc","bcd","rfh","hal"] -> "abcdrfhal"
["mmm","qqq","rrr"] -> "mmmqqqrrr"
["abcbc","bcbcd"] -> "abcbcd"
["aXc","bXd"]    -> "aXcbXd"
["abc","bcd","cde"] -> "abcde"
["abcd","bc"] -> "abcdbc"
["abcde", "cde", "abcde"] -> "abcdeabcde"
```

SQL (Postgres) [SQL (Postgres)](https://www.postgresql.org/docs/12/sql.html), ~~394~~ 320 bytes

Jack Douglas

APL (Dyalog Unicode) [APL (Dyalog Unicode)](https://www.dyalog.com/), 32 [bytes](https://codegolf.meta.stackexchange.com/a/9429/43319 "When can APL characters be counted as 1 byte each?") ([SBCS](https://github.com/abrudz/SBCS ".dyalog files using a single byte character set"))

Adám

Top Answer SQL (Postgres)

Jack Douglas

# [SQL (Postgres)](https://www.postgresql.org/docs/12/sql.html), ~~394~~ 320 bytes

```sql
with recursive w as(select v,o,c,substr(v,1,c-1)s,substr(v,c)e from unnest((select v from a))with ordinality a(v,o),generate_series(1,length(v)+1)c),z(k,m,n)as(select o,v,v from w where o=1and c=1union all select o,v,n||e from w join z on o=k+1and right(m||e,length(v))=v)select n from z order by k desc,length(n)limit 1
```

<>https://dbfiddle.uk/?rdbms=postgres_12&fiddle=2aa574c368bbf4514e3d697419697b4c

1. (`with recursive w as…`): generate a set containing multiple rows for each element of the array, one for each character in the string, including the original string and the start and end of the string split on the character number
2. (`, z(k,m,n) as…`): use recursive sql to concatenate each possible combination of string endings and eliminate those that do not match the overlap condition
3. (`…order by k desc, length(n) limit 1`): we only want the shortest element in the final recursion


(Minus 74 bytes thanks to Andriy M)

Answer #2 APL (Dyalog Unicode)

Adám

# [APL (Dyalog Unicode)], 32 [bytes](https://codegolf.meta.stackexchange.com/a/9429/43319 "When can APL characters be counted as 1 byte each?") ([SBCS](https://github.com/abrudz/SBCS ".dyalog files using a single byte character set"))

Anonymous tacit prefix function

```apl
⊃{(⌽'$',⍨'$',⍨¨,\⍵)⎕R⍵⍠'ML'1⊢⍺}/
```

[Try it online!][TIO-k88mekmn]

`⊃{`…`}/` insert the following function between the elements:

&emsp;`⊢⍺` on the left argument
 
&emsp;`(`…`)⎕R⍵⍠'ML'1` Replace the first occurrence of the following with the right argument:

&emsp;&emsp;`,\⍵` the prefixes of the right argument

&emsp;&emsp;`'$',⍨¨` append a dollar sign (indicating end of line) to each

&emsp;&emsp;`'$',⍨` append a dollar sign (indicating end of line)

&emsp;&emsp;`⌽` reverse (to search for the longest prefix first


[APL (Dyalog Unicode)]: https://www.dyalog.com/
[TIO-k88mekmn]: https://tio.run/##SyzI0U2pTMzJT////1FXc7XGo5696irqOo96V0CpQyt0Yh71btV81Dc1CEg/6l2g7uujbvioa9Gj3l21@v/THrVNeNTbB9T8qHfNo94th9YbP2qbCFQdHOQMJEM8PIP/p6knJiWrK6gnJacAyaK0DCCZkZijzpWmnpubC@QUFhaCJIqKQEJAtVDVIPUggQgwNyIFKgs3KTklFSqUAhaDcVKhcgpQHgA "APL (Dyalog Unicode) – Try It Online"

2 Answers