19
\$\begingroup\$

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

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

13 Answers 13

6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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)

\$\endgroup\$
1
  • \$\begingroup\$ Turns out * doesn't do what I expect, but it still works. (as long as b is not empty...) \$\endgroup\$
    – DELETE_ME
    Feb 13, 2021 at 13:17
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
1
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 22 bytes

I↨E⌕Aθη⊙↔⁻⌕Aθηι∧λ‹λLη¹

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

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

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

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Perl 5 (-00p), 54 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.