Matching ABACABA-type patterns

Question

(This challenge is related to the challenge "Generate the Abacaba sequence.")

Zimin words (also called "sesquipowers") are an important idea in the subject of "combinatorics on words". This is because every Zimin word is "unavoidable", meaning that every sufficiently long word over a finite alphabet has a substring that is an "instance" (defined below) of the Zimin word. Remarkably, every binary word of length 29 has a substring that is an instance of the pattern \$ABACABA\$.

Definitions

Zimin words are recursively defined:

• \$Z_1 = A\$
• \$Z_2 = ABA\$
• \$Z_3 = ABACABA\$
• \$Z_4 = ABACABADABACABA\$
• \$\vdots\$
• \$Z_{n+1} = Z_n X Z_n\$

It's a little tricky to formally define what it means to be an "instance" for a word without talking about free monoids and homomorphisms, but it's easy enough to see from some examples. At a hand-wave-y level, a word \$w\$ is said to be an "instance" of a pattern if there's a way to assign a (non-empty) string to each letter of the pattern and recover \$w\$.

Examples

Consider the word "11211212211221" on two letters.

• It has \$105\$ substrings that are instances of the Zimin word \$Z_1 = A\$ because every substring is an instance of \$A\$.
• It has \$54\$ substrings that are instances of the Zimin word \$Z_2 = ABA\$—for example, the substring "212211221": $$ 11211\underbrace{21}_A\underbrace{22112}_B\underbrace{21}_A. $$
• It has \$1\$ substring that is an instance of the Zimin word \$Z_3 = ABACABA\$: $$ 11 \underbrace{2}_A \underbrace{11}_B \underbrace{2}_A \underbrace{12}_C \underbrace{2}_A \underbrace{11}_B \underbrace{2}_A 21. $$
• It has \$0\$ substrings that are instances of the Zimin word \$Z_4 = ABACABADABACABA\$.

Thus if you are given "11211212211221", you should return [105, 54, 1].

Challenge

This code-golf challenge will give you a word as an an input, and asks you to output a list of the number of substrings that are instances \$Z_1, Z_2, \cdots, Z_n\$ until there are not any substrings that are instances. That is, your program should never output 0.

You can take the word in any reasonable way: as a string, as a list of strings, as a list of appropriately coded integers, as a pair of integers \$(b,i)\$ where \$i\$ is base-\$b\$ encoded integer, etc.

Test Data

word                           | zimin_counts(word)
-------------------------------+-------------------
""                             | []
"P"                            | [1]
"MOM"                          | [6,1]
"alfalfa"                      | [28, 8]
"aha aha!"                     | [36, 9, 1]
"xxOOOxxxxxOOOxxx"             | [136, 64, 9]
"3123213332331112232"          | [190, 55, 1]
"2122222111111121221"          | [190, 80, 3]
"13121311213121311212"         | [210, 114, 25, 2]
"344112222321431121114"        | [231, 48]
"141324331112324224341"        | [231, 49]
"344342224124222122433"        | [231, 61, 1]
"331123321122132312321"        | [231, 74]
"11221112211212122222122"      | [276, 149, 4]
"2222222112211121112212121"    | [325, 166, 6]
"AAAaaAAAAAAAaAaAAaAaAAAAA"    | [325, 198, 30]
"1100000010010011011011111100" | [406, 204]
"1111221211122111111221211121" | [406, 261, 56, 2]

Answer 1

J, ^{63 58 53 52 51} 47 bytes

_1}.1#.a:~:[:([#~[e.&,(],,)&.>/)^:a:~@;<@(<\)\.

Try it online!

^{-2 bytes thanks to Bubbler}

^{-3 bytes thanks to FrownyFrog for golfier way to create all substrings of a string.}

how

We'll use MOM as our example:

• [:...;<@(<\)\. All substrings of the input, boxed.

  ┌─┬─┬─┬──┬──┬───┐
  │M│O│M│MO│OM│MOM│
  └─┴─┴─┴──┴──┴───┘
  

• (...)^:a:~ Using the substrings as both the left and right args ~, apply the verb in parens until a fixed point, keeping track of each iteration's results ^:a:.

• (...(],,)&.>/) To create the next "level" of candidates, create all possible combinations that look like <level_n><orig substring><level_n> where level_n is any element from the current level, and <orig substring> is one of the original input substrings (level 0). Then the 1st level looks like:

  ┌─────┬─────┬─────┬───────┬───────┬─────────┐
  │MMM  │OMO  │MMM  │MOMMO  │OMMOM  │MOMMMOM  │
  ├─────┼─────┼─────┼───────┼───────┼─────────┤
  │MOM  │OOO  │MOM  │MOOMO  │OMOOM  │MOMOMOM  │
  ├─────┼─────┼─────┼───────┼───────┼─────────┤
  │MMM  │OMO  │MMM  │MOMMO  │OMMOM  │MOMMMOM  │
  ├─────┼─────┼─────┼───────┼───────┼─────────┤
  │MMOM │OMOO │MMOM │MOMOMO │OMMOOM │MOMMOMOM │
  ├─────┼─────┼─────┼───────┼───────┼─────────┤
  │MOMM │OOMO │MOMM │MOOMMO │OMOMOM │MOMOMMOM │
  ├─────┼─────┼─────┼───────┼───────┼─────────┤
  │MMOMM│OMOMO│MMOMM│MOMOMMO│OMMOMOM│MOMMOMMOM│
  └─────┴─────┴─────┴───────┴───────┴─────────┘
  

• [#~[e.&,... Check if each original substring is an element of this candidate list [e.&,, and use that to filter the original substrings [#~. In the above example, only MOM passes.

• After the above process iterates to its fixed point (no more matches), the result is:

  ┌───┬─┬─┬──┬──┬───┐
  │M  │O│M│MO│OM│MOM│
  ├───┼─┼─┼──┼──┼───┤
  │MOM│ │ │  │  │   │
  ├───┼─┼─┼──┼──┼───┤
  │   │ │ │  │  │   │
  └───┴─┴─┴──┴──┴───┘
  

• a:~: Since we don't want to count empty boxes, we perform an elementwise test for "not equal to the empty box a:", giving us a 0-1 matrix:

  1 1 1 1 1 1
  1 0 0 0 0 0
  0 0 0 0 0 0
  

• 1#. Sum rows:

  6 1 0
  

• _1}. And kill the last element:

  6 1
  

Answer 2

JavaScript (ES6),  148 142  141 bytes

Saved 6 bytes thanks to @user81655

Expects an array of characters.

f=(a,o=[],s='')=>a.map(c=>{for(s+=c,i=p='';s.match(`^${p+='(.+)'+p.replace(/\(.../g,_=>"\\"+n++)}$`);n=1)o[+i]=-~o[i++]})+a?f(a.slice(1),o):o

Try it online!

How?

For each substring in the input string, we apply the following patterns while they match:

P₀  ^(.+)$
P₁  ^(.+)(.+)\1$
P₂  ^(.+)(.+)\1(.+)\1\2\1$
P₃  ^(.+)(.+)\1(.+)\1\2\1(.+)\1\2\1\3\1\2\1$
    ...

Apart from the delimiters ^ and $ which are ignored below, these patterns are built recursively as follows:

• \$P_0\$ is (.+)

• \$P_{k+1}\$ is \$P_{k}\$, followed by (.+), followed by \$P_k\$ with each \$n\$-th group (.+) replaced with the back reference \{n} (1-indexed)

  e.g. for \$P_2 \rightarrow P_3\$:

  (.+)(.+)\1(.+)\1\2\1 -> (.+)(.+)\1(.+)\1\2\1 (.+) (.+)(.+)\1(.+)\1\2\1
                                                     \1  \2    \3

It's worth noting that:

• if a substring matches some \$P_i\$, it also matches all \$P_j,\:j<i\$
• if a substring doesn't match some \$P_i\$, it also won't match any \$P_j,\:j>i\$

We keep track of the results in the array o[], which is eventually returned. Whenever \$P_i\$ matches a substring, we increment o[i].

Answer 3

Brachylog, 30 bytes

{s{h∧1|~cṪ↺₁hʰb=h↰ᶠ⌉+₁}ᵘ}ᶠcọtᵐ

Try it online!

• {s … }ᶠ for every substring:
• {h∧1| …} on every non-empty string, return 1. Also try …
• ~c input split into groups, so that …
• Ṫ↺₁…b= it unifies with [A,B,A] (this works, too, but is sadly longer).
• hʰ B is non-empty
• h↰ᶠ take A and call the predicate recursively, finding all results
• ⌉+₁ get the highest number and add 1
• ᵘ Find all unique values. So for aha aha we get [1,2,3] from [aha aha, aha, a].
• cọtᵐ join the results from all the substrings, count the occurrences of each number, and return them

Answer 4

Retina, 77 bytes

K`(.+)
/\(/{G`
%"$+"~`^
w`
"¶0"(Am`^0
K`

$+2
(.*?\))+(.*)$
$&¶$&(.+)$2\$#1$2

Try it online! No test suite because of the advanced use of result history. Explanation:

K`(.+)

Start by considering matches of Z₁.

/\(/{`

Repeat while the working area contains a (.

G`

Do nothing. This is here solely to record the value at the start of each pass of the loop in the stage history, so that it can be referred to later on.

%"$+"~`^
w`

Processing each line of regex separately, evaluate it as an overlapped count command on the original input, thereby returning a list of counts.

"¶0"(`

If the list contains a 0 (strictly speaking this can only happen on the second pass, as I use a newline to check that it's a leading 0)...

Am`^0

... then delete all 0 values (including the first if the input string was empty), otherwise:

K`

$+2

Retrieve the value saved in step 2. (Because Retina numbers stages in post-order traversal, this is the G command.) Unfortunately $ doesn't work directly in a K command, so the easiest way to do this is to delete the result and then substitute the empty string with the saved value.

(.*?\))+(.*)$
$&¶$&(.+)$2\$#1$2

Append an additional regex that matches the next Zimin word.

Answer 5

05AB1E, 31 bytes

āεo<VŒε.œYùεĆ4ô€¨yªεÂQ}P}1å]O0Ü

Try it online or verify some more test cases (pretty slow, so the larger test cases are omitted in the test suite).

Explanation:

Step 1: Loop over the possible sizes \$n\$ of the \$Z_n\$ based on the input-length.^†

We can calculate the valid \$n\$ to check with the following formula: \$m = \left\lceil\log_2(L)\right\rceil\$, where \$L\$ is the input-length, and the result \$m\$ indicates the range \$[1,m]\$ to check for Zimin 'words': \$Z_{n=1}^m\$.

In 05AB1E code, this would have resulted in g.²îLεo<VŒε.œYùεĆ4ô€¨yªεÂQ}P}1å]O0Ü (35 bytes): try it online.

^† Since we have to strip trailing 0s at the end in case no \$Z\$ were found for them anyway, we simply don't calculate this maximum. Instead, we'll just check in the range \$[1,L]\$ for Zimin words. Less efficient in terms of performance, but 4 bytes shorter, which is all we care about with code-golf. :)

We can also calculate the amount of parts in the resulting Zimin 'word' (\$Z_n\$), which is the oeis sequence A000225: \$2^n-1\$.

ā              # Push a list in the range [1, (implicit) input-length]
 ε             # Map over each of these integers:
  o            #  Take 2 to the power this integer
   <           #  Decrease it by 1
    V          #  Pop and store this in variable `Y`

Step 2: For each of these amount of parts \$Y\$, we check how many substrings of the input are valid Zimin 'words' (\$Z_Y\$).

Step 2a: We do this by first generating all substrings of the input, and mapping over them:

  Π           #  Get all substrings of the (implicit) input-list
   ε           #  Inner map over each substring:

Step 2b: Then we'll get all partitions of the current substring of exactly \$Y\$ amount of parts:

    .œ         #   Get all partitions of this subtring
      Yù       #   Only leave the partitions of `Y` amount of parts

Step 2c: We then check for each of these (correctly sized) partitions of this substring if it's a valid Zimin 'word'.
We do this by checking two things:

1. Is the current list of parts in this partition a palindrome?
2. Is every \$ABA\$ part within the current partition a palindrome?

As for step 2c2, we do so by first adding a dummy trailing item to the partition; then splitting the partition-list into sublists of size 4; then we remove the trailing item from each of these sublists; after which we can check for each \$[A,B,A]\$ sublist whether it's a palindrome.

        ε      #   Inner map over each remaining partition:
         Ć     #    Enclose the partition; append its own first part at the end
          4ô   #    Split the partition into parts of size 4
            ۬ #    Remove the final part of each quartet
         yª    #    Append the full partition to this list of triplets as well
           ε   #    Inner map over this list of lists:
               #     Check if the current list is a palindrome by:
            Â  #      Bifurcating: short for Duplicate & Reverse copy
             Q #      Check if the list and reversed copied list are the same
           }   #    After this inner-most map:
            P  #    Check if all were truthy by taking the product

Alternatively for step 2c2, Ć4ô€¨ could have been 4ô3δ∍ instead: Split the partition-list into sublists of size 4 (with 3 in the trailing sublist); shorten each sublist to size 3 by removing trailing item(s); same as above. Try it online.

Step 2d: And we then check if there is at least one valid Zimin 'word' (\$Z_Y\$) among the mapped partitions for this substring:

       }       #   After the map over the partitions of the current substring:
        1å     #   Check if any were truthy by checking if it contains a 1
               #   (NOTE: we can't use the max builtin `à` here like we usually do when
               #    we want to mimic an `any` builtin, because lists could be empty here,
               #    resulting in an empty string)

Step 3: Now we sum the amount of truthy results per size \$Y\$:

]              # Close all remaining nested maps
 O             # Sum the inner-most lists together

Step 4: And finally we clean-up all trailing 0s (both the \$\geq m\$ sizes we've checked in our golfed approach, as well as any trailing \$Z\$ within the \$[1,m]\$ range that simply resulted in \$0\$), before outputting the result:

  0Ü           # Remove any trailing 0s from this list
               # (after which the resulting list is output implicitly)

Answer 6

Python 3, 205 bytes

def f(w):
 R=range(len(w));s=[w[i:j+1]for i in R for j in R[i:]];v=[*s];n=len(s);r=[]
 while n:r+=[n];s={i+j+i for i in s for j in v if i+j+i in w};n=sum(len({w.find(a,b)for b in R})-1for a in s)
 return r

Try it online!

Quite verbose.
Inputs a string and returns a list of the number of substrings that are instances \$Z_1, Z_2, \dots, Z_n\$.

Answer 7

Wolfram Language (Mathematica), 66 bytes

Counts@Level[z@@@Subsequences@#,-3]&
z[Longest@a___,__,a___]:=z@a!

Try it online!

Returns an Association with corresponding values. Prepend List@@ for list output.