# Count strictly overlapping substrings

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

• Sandbox Feb 13, 2021 at 12:49
• ... Can we assume that b is empty? Feb 13, 2021 at 13:17
• @user202729 clarified (assuming you meant "can we assume that b isn't empty") Feb 13, 2021 at 13:52
• Suggest a test case where a begins with a single occurrence of b and later contains overlapped bs. eeheeee Feb 14, 2021 at 17:45

# 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

# 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


# MATL, 13 bytes

yXf&-|wn<s1>s


Inputs are in reverse order: b, then a.

### 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).

# 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)

• Turns out * doesn't do what I expect, but it still works. (as long as b is not empty...) Feb 13, 2021 at 13:17

# 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


# 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.

# 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!

• Nice! You can still save a byte using el... Feb 15, 2021 at 23:12

# 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! # 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. # 05AB1E, 18 bytes .sIÅ?ƶ0KDδαIg‹O1›O  Port of @JonathanAllan's Jelly answer. 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)  # 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  # Perl 5 (-00p), 54 bytes $_=/
(.+)(.*\1)$/?()=/(?=$1$2$2)|(?<=$1)$2$2(?!$2)/g:0


Try it online!

# 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
`