Find Patterns in Strings

Question

In this challence, your task is to locate substrings with a given structure.

Input

Your input shall be two non-empty alphanumeric strings, a pattern p and a text t. The idea is that each character of p represents a contiguous non-empty substring of t which occur next to each other, and p represents their concatenation. Identical characters correspond to identical substrings; for example, the pattern aa represents any non-empty square (a string obtained by concatenating a shorter string to itself). Thus the pattern aa can match the substring byebye, with each a matching bye.

Output

If the text t contains a substring that p matches, then your output shall be that substring, with colons : inserted between the strings that correspond to characters of p. For example, if we have t = byebyenow and p = aa, then bye:bye is an acceptable output. There may be several choices for the matching substring, but you shall only output one of them.

If t does not contain a matching substring, your output shall be a sad face :(.

Rules and Clarifications

Different characters of p can correspond to identical substrings, so p = aba can match the string AAA. Note that the characters must correspond to non-empty strings; in particular, if p is longer than t, the output must be :(.

You can write a full program or a function, and you can also change the order of the two inputs. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

Given in the format pattern text -> output. Note that other acceptable outputs may exist.

a Not -> N
aa Not -> :(
abcd Not -> :(
aaa rerere -> re:re:re
xx ABAAAB -> A:A
MMM ABABBAABBAABBA -> ABBA:ABBA:ABBA
x33x 10100110011001 -> 10:1001:1001:10
abcacb 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> c:a0aa:0c:c:0c:a0aa
abccab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> a:a:0c0:0c0:a:a
abcbcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> :(
abcbdcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> 00:c:ca0aa0c:c:0:ca0aa0c:00:c

Answer 1

Python, 207 bytes

import re
h=lambda x:"a"+str(ord(x))
def g(a,b):
 c,d="",set()
 for e in a:
  c+=["(?P<"+h(e)+">.+)","(?P="+h(e)+")"][e in d]
  d.add(e)
 f=re.search(c,b)
 return f and":".join(f.group(h(e))for e in a)or":("

Call with g(pattern, string)

Uses the re module to do most of the work.

Answer 2

JavaScript (SpiderMonkey) (ES5.1), 198 bytes

Since ES6 was released in June 2015, I post the ES5.1 version of the code together with the ES6 equivalent, but declare ES5.1 version as the main answer.

Greedy match, so the first case returns "Not" instead of "N".

function(a,b){c=[o="indexOf"];r=a.split("");return(m=RegExp(r.map(function(i){return(e=c[o](i))>0?"\\"+e:(c.push(i),"(.+)")}).join("")).exec(b))?r.map(function(x){return m[c[o](x)]}).join(":"):":("}

Try it online!

JavaScript (Node.js) (ES6), 141 bytes

a=>b=>(c=[o="indexOf"],r=[...a],m=RegExp(r.map(i=>(e=c[o](i))>0?"\\"+e:(c.push(i),"(.+)")).join``).exec(b))?r.map(x=>m[c[o](x)]).join`:`:":("

Try it online!

Takes the arguments in currying syntax: f(a)(b)

Explanation (and ungolfed):

function matchPattern(a, b) {                   // Main function
 var c = ["indexOf"];                           // Array used for the capturing groups
 var r = [...a];                                // Split the pattern first
 var m = RegExp(r.map(function(i) {             // Create the regex
  var e = c.indexOf(i);                         // Check if the character is found before
  if (e > 0)                                    // If so
   return "\\" + e;                             // Append the back reference to the regex
  else {                                        // If not
   c.push(i);                                   // Append the character to the array
   return "(.+)";                               // Append a capturing group to the regex
  }             
 }).join("")).exec(b);                          // Execute the regex
 if (m != null)                                 // If the pattern matches the string
  return r.map(function(x) {                    // Replace each letter
   return m[c.indexOf(x)];                      // With the corresponding substring
  }).join(":");                                 // And join them with ":"
 else                                           // If there is no match
  return ":(";                                  // Return ":("
}

Answer 3

Brachylog, 35 bytes

sᵗ~cᵗXlᵛ∧Xzdz≠ʰ∧Xt~ṇ{Ḷ∧":"|}ᵐ.∨":("

Try it online!

On not-quite-small inputs, very slow. I-haven't-actually-done-the-sixth-test-case-but-not-for-lack-of-trying slow. (Probably owing to brute-forcing every partition of every substring, starting with the largest, and then checking if it's a match.) Takes input as a list [pattern,string].

Condensed and divided explanation:

sᵗ~cᵗX

X is the pattern paired with a partition of a substring of the input string.

lᵛ

The pattern and the partition have the same number of elements.

Xzdz≠ʰ

No two unique pattern char, matched substring pairs share a pattern character. That is, no pattern character maps to multiple substrings, although multiple pattern characters may map to one substring.

Xt~ṇ{Ḷ∧":"|}ᵐ.∨":("

The output is the elements of the partition joined by colons, unless something couldn't be done, in which case it's :( instead.

Monolithic explanation:

                                       The input
 ᵗ  ᵗ                                  with its last element replaced with
  ~c                                   a list which concatenates to
s                                      a substring of it
     X                                 is X,
       ᵛ                               the elements of which all have the same
      l                                length.
        ∧                              And,
         X                             X
          z                            zipped
           d                           with duplicate pairs removed
            z                          and zipped back
              ʰ                        has a first element
             ≠                         with no duplicate values.
               ∧                       Furthermore,
                 t                     the last element of
                X                      X
                  ~ṇ                   with its elements joined by newlines
                    {      }ᵐ          where each character of the joined string
                     Ḷ                 is a newline
                      ∧                and
                          |            is replaced with
                       ":"             a colon
                          |            or is passed through unchanged
                             .         is the output.
                              ∨        If doing any part of that is impossible,
                                       the output is
                               ":("    ":(".