Count strictly overlapping substrings

Question

Given two strings a and b, count how many times b occurs as a substring in a, but only when it overlaps with another instance of b.

(This means that 1 will never be a valid output, because in order for the substring to be strictly overlapping, there must be at least one other instance for it to overlap with.)

Test cases

input a              input b     output

trololololol         trol        0
trololololol         ol          0
trololololol         lol         4
trololololol         LOL         0
HAAAAHAAAAA          A           0
HAAAAHAAAAA          AA          7
Teeheeee             ee          3
123123123123123123   12312312    4
(empty string)       whatever    0

b will never be an empty string.

Rules

• Matching must be case-sensitive
• You may use any sensible IO format
• Standard loopholes apply
• This is code-golf, so the shortest code in bytes wins.

Answer 1

J, ^{35 33 31} 24 bytes

1#.1<1#.#@[>|@-//~@I.@E.

Try it online!

-7 bytes after reading Luis Mendo's idea and realizing I could adapt it to J

• I.@E. Indexes of matches
• |@-//~@ Table of pairwise absolute differences
• #@[> Is it less than the substring length? (produces 0-1 table)
• 1#. Sum rows
• 1< Greater than 1? (produces 0-1 list)
• 1#. Sum

Answer 2

JavaScript (ES6), 69 bytes

Expects (a)(b).

a=>g=(b,i=(t=0)-.1,p)=>~i?g(b,a.indexOf(b,i+1),i,q=b[i-p]?t-=~!q:0):t

Try it online!

How?

Given the last position i of b in a, we use a.indexOf(b, i + 1) to get the position of the next occurrence. We keep track of the previous position in p and figure out whether they overlap by testing if b[i - p] is defined.

At the very beginning of the process, we initialize i to -0.1 so that it's neither -1 (that would stop the recursion) nor 0 that would mean that there's a match at position 0, while still being interpreted as 0 by .indexOf().

Exemple for a = "XABABA" and b = "ABA":

 iteration |         1 |        2 |    3 |   4
-----------+-----------+----------+------+-----
         i |      -0.1 |        1 |    3 |  -1
         p | undefined |     -0.1 |    1 |   3
     i - p |       NaN |      1.1 |    2 | n/a
     match |  "XABABA" | "XABABA" | none | n/a
                ^            ^

Commented

a =>                // outer function taking the haystack a
g = (               // inner recursive function g taking:
  b,                //   b = needle
  i = (t = 0) - .1, //   i = pointer in a, initialized to -0.1
                    //   t = output, initialized to 0
  p                 //   p = position of the previous occurrence
) =>                //
  ~i ?              // if i is not equal to -1:
    g(              //   do a recursive call:
      b,            //     pass b unchanged
      a.indexOf(    //     set i = position of the next occurrence
        b,          //       of b in a
        i + 1       //       starting at i + 1 (for the first iteration,
      ),            //       this gives -0.1 + 1 = 0.9, rounded to 0)
      i,            //     set p = i
      q =           //     the flag q is set to 0 if this is the first
                    //     occurrence in a chain of valid matches:
        b[i - p] ?  //       if i - p is less than the length of b:
          t -= ~!q  //         add 2 to t if q = 0, or only 1 otherwise
                    //         either way, set q to a non-zero value
        :           //       else:
          0         //         set q to 0
    )               //   end of recursive call
  :                 // else:
    t               //   stop the recursion and return t

Answer 3

MATL, 13 bytes

yXf&-|wn<s1>s

Inputs are in reverse order: b, then a.

Try it online! Or verify all test cases.

Explanation

Consider inputs 'lol' and 'trololololol' as an example.

y     % Implicit inputs: b, a. Duplicate second-top element in stack
      % STACK: 'lol', 'trololololol', 'lol'
Xf    % Find second string in first string. Produces a row vector (possibly
      % empty) with the indices of all occurrences of b in a
      % STACK: 'lol', [4 6 8 10]
&-    % Square matrix of pairwise differences
      % STACK: 'lol', [0 2 4 6; -2 0 2 4; -4 -2 0 2; -6 -4 -2 0]
|     % Absolute value, element-wise
      % STACK: 'lol', [0 2 4 6; 2 0 2 4; 4 2 0 2; 6 4 2 0]
w     % Swap
      % STACK: [0 2 4 6; 2 0 2 4; 4 2 0 2; 6 4 2 0], 'lol'
n     % Number of elements
      % STACK: [0 2 4 6; 2 0 2 4; 4 2 0 2; 6 4 2 0], 3
<     % Less than? Element-wise
      % STACK: [1 1 0 0; 1 1 1 0; 0 1 1 1; 0 0 1 1]
s     % Sum of each column. For each ocurrence, this gives the number of
      % occurrences, including itself, that are close enough to overlap.
      % If there are no occurrences this gives 0
      % STACK: [2 3 3 2]
1>    % Greater than 1? Element-wise. For each occurrence, this gives 1 (true)
      % if there is a different occurrence that is close enough to overlap
      % STACK: [1 1 1 1]
s     % Sum. Implicit display
      % STACK: 4

(Note that the code 1>s cannot be replaced by qz because when there are no occurrences of b in a that would give 1 instead of 0, due to the behaviour of the previous s).

Answer 4

Python 3.8 (pre-release), 102 bytes

lambda a,b:sum(b==a[i-1:i+(T:=len(b)-1)]*(b in a[i+~T:i+T-1]or b in a[i:i+T*2])for
i in range(len(a)))

Try it online!

Explanation: it's pretty readable already. Just that i+~T == i-T-1, and the := is equivalent to an assignment but can be inserted in a lambda (to make the code shorter)

Answer 5

Jelly, 15 bytes

wÐƤẹ1ạ€`<L}S>1S

A dyadic Link accepting a on the left and b on the right which yields the count.

Try it online! Or see the test-suite.

How?

wÐƤẹ1ạ€`<L}S>1S - Link: a, b
 ÐƤ             - for postfixes (of a):
w               -   first 1-indexed index (of b)
   ẹ1           - indices of 1 (i.e. X = a list of starts of b in a)
       `        - use (X) as both arguments of:
      €         -   for each (v in X):
     ạ          -     (v) absolute difference (across each of X)
                  -> list of lists of distances between starts
         L}     - length (of b)
        <       - less than
           S    - sum
            >1  - greater than 1 (i.e. not just overlapping itself)
              S - sum

Answer 6

Retina 0.8.2, 43 bytes

(?=(.+)(.*¶)\1$)(.(?!\2))+?((?=\1)|(?<=\1))

Try it online! Takes input on separate lines but link includes test suite that splits on comma for convenience. Explanation: The program consists of a single match stage that outputs the count of matches of the pattern within the string a. For each match:

(?=(.+)(.*¶)\1$)

The remainder of the string a is split into two parts, the first of which must equal string b (which is therefore effectively captured into $1). The part of the string a after this match of the string b is captured into $2.

(.(?!\2))+?

Advance as few characters as possible, and definitely without reaching the end of this particular match of string b in string a.

((?=\1)|(?<=\1))

Find an overlapping match of string b. Note that in the case of a forward overlap, the lazy quantifier ensures that this match will always stop on or before the next match of string b.

Answer 7

R, 90 89 bytes

function(x,y,z=rle(diff(el(gregexpr(paste0("(?=",y,")"),x,,T)))<nchar(y)))sum(z$l[z$v]+1)

A byte saved by Dominic van Essen.

Try it online!

Answer 8

Perl 5, 117 bytes

sub f{($a,$b,$f,%s,$c)=@_;!$s{$x=1+index$a,$b,$_}++&&$x&&($w=$f&&$x-$f<length$b,$f=$x,$c+=$j*$w,$j=2-$w)for 0..99;$c}

Try it online!

Answer 9

Charcoal, 22 bytes

Ｉ↨Ｅ⌕Ａθη⊙↔⁻⌕Ａθηι∧λ‹λＬη¹

Try it online! Link is to verbose version of code. Explanation: Conveniently, Charcoal's FindAll command also includes overlapping matches.

     θ                  First input
      η                 Second input
   ⌕Ａ                   Find all matches
  Ｅ                     Map over positions
          ⌕Ａθη          All matches
        ↔⁻              Absolute difference with
              ι         Current match
       ⊙                Does any difference satisfy
                λ       Current difference
               ∧        Non-zero and
                  λ     Current difference
                 ‹      Less than
                   Ｌ    Length of
                    η   Second string
 ↨                   ¹  Take the sum
Ｉ                       Cast to string
                        Implicitly print

I don't use Sum here because it doesn't output 0 for an empty list.

Answer 10

05AB1E, 18 bytes

.sIÅ?ƶ0KDδαIg‹O1›O

Port of @JonathanAllan's Jelly answer.

Try it online or verify all test cases.

Explanation:

.s                  # Get all suffices of the (implicit) input-string
  IÅ?               # Check for each if they start with the second input-string
                    # (1 if truthy; 0 if falsey)
     ƶ              # Multiply each value by their 1-based index
      0K            # Remove all 0s
         δ          # Apply double-vectorized,
        D           # with a copy of itself:
          α         #  Get the absolute different between the values
           Ig‹      # Check for each that it's lower than the length of the second input
              O     # Sum the checks of each row together
               1›   # Check for each whether it's larger than 1
                 O  # And sum those checks together again
                    # (after which the result is output implicitly)

Answer 11

APL(Dyalog Unicode), 20 bytes ^SBCS

+/1<1⊥≢⍤⊣>∘|∘.-⍨⍤⍸⍤⍷

Try it on APLgolf!

A train submission which takes b on the left, and a on the right.

-2 bytes from Adám(helped trainify the function)

Explanation

                   ⍷ boolean array where b occurs in a
                 ⍸⍤  indices of 1s in it
            ∘.-⍨⍤    all pairwise differences
           |         take the absolute value of it(vectorized)
      ≢⍤⊣            length of b        
         >           greater than the absolute values?(vectorizes)
    1⊥               sum the columns of that result
  1<                 are they >1?                                  
+/                   sum the result

Answer 12

Perl 5 (-00p), 54 bytes

$_=/
(.+)(.*\1)$/?()=/(?=$1$2$2)|(?<=$1)$2$2(?!$2)/g:0

Try it online!

Answer 13

Japt, 12 bytes

Been quite a while since I've done any Japt, probably has some room for improvement.

ðV
äÏ-X<Vl
è

Try it out here.

Explanation:

ðV      # Get all indices of needle in input
äÏ-X<Vl # For every consecutive pair in the result, check if their distance is small enough that they overlap
è       # Return the number of items that were true