Skills101
← All coding problems

Count Pattern Occurrences

mediumStrings II+20 XPTime limit 2s

A plagiarism checker needs to know how many times a pattern appears inside a long text. Count all occurrences, including overlapping ones: aa appears 3 times in aaaa, and aba appears twice in ababa.

Input:

  • line 1: the text
  • line 2: the pattern

Both contain only lowercase letters.

Output: the number of positions where the pattern occurs in the text.

Constraints: 1 ≤ pattern length ≤ text length ≤ 10⁵. Comparing the pattern at every position can take 10¹⁰ steps on texts like aaaa…a — too slow.

Think about it: KMP. Compute the prefix function of pattern + '#' + text: pi[i] is the length of the longest proper prefix of the string that also ends at position i. Every position in the text part where pi[i] equals the pattern length is the end of one occurrence. The whole thing is O(n + m).

Sample input 1

aaaa
aa

Sample output 1

3

Sample input 2

ababa
aba

Sample output 2

2

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.