{ }codelper
finding textP0030

Count overlapping occurrences

The first line gives a text and the second line gives a pattern.
Print how many times the pattern occurs in the text.
Occurrences that overlap are counted separately.
For example "aa" occurs in "aaaa" 3 times, starting at positions 0, 1 and 2.
If the pattern is longer than the text, the answer is 0.

Input
text: lowercase letters, length 1 to 5,000.
pattern: lowercase letters, length 1 to 10
Output
the number of occurrences
Example 1 · stdin
aaaa
aa
stdout
3
Example 2 · stdin
abababa
aba
stdout
3
main.py
Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 8 languages

Built-in "how many times" functions count without overlap: Python text.count("aa") gives 2 for "aaaa".
To count overlaps, search again from the cell right after the match (+1): Python text.find(p, i + 1), JS/TS/Java indexOf(p, i + 1), C# IndexOf(p, i + 1, StringComparison.Ordinal), C++ find(p, i + 1), C strstr(q + 1, p) (it returns a pointer to the match).
Craykon's IndexOf takes no start position, so compare text.Substring(i, m) == pattern at every position.
Trap: skipping the whole pattern length (+m) after a match misses overlaps, just like the built-in count.

Pythonmain.py · 8 lines
text = input()pattern = input()count = 0i = text.find(pattern)while i != -1:    count += 1    i = text.find(pattern, i + 1)print(count)
JavaScriptmain.js · 4 lines
const [text, pattern] = require("fs").readFileSync(0, "utf8").split("\n").map((s) => s.trim());let count = 0;for (let i = text.indexOf(pattern); i !== -1; i = text.indexOf(pattern, i + 1)) count++;console.log(count);
TypeScriptmain.ts · 5 lines
import { readFileSync } from "node:fs";const [text, pattern]: string[] = readFileSync(0, "utf8").split("\n").map((s) => s.trim());let count = 0;for (let i = text.indexOf(pattern); i !== -1; i = text.indexOf(pattern, i + 1)) count++;console.log(count);
JavaMain.java · 13 lines
import java.io.BufferedReader;import java.io.InputStreamReader; public class Main {    public static void main(String[] args) throws Exception {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        String text = br.readLine().trim();        String pattern = br.readLine().trim();        int count = 0;        for (int i = text.indexOf(pattern); i != -1; i = text.indexOf(pattern, i + 1)) count++;        System.out.println(count);    }}
C#Main.cs · 15 lines
using System; class Program{    static void Main()    {        string text = Console.ReadLine().Trim();        string pattern = Console.ReadLine().Trim();        int count = 0;        for (int i = text.IndexOf(pattern, StringComparison.Ordinal); i != -1;             i = text.IndexOf(pattern, i + 1, StringComparison.Ordinal))            count++;        Console.WriteLine(count);    }}
C++main.cpp · 10 lines
#include <iostream>#include <string> int main() {    std::string text, pattern;    std::cin >> text >> pattern;    int count = 0;    for (size_t i = text.find(pattern); i != std::string::npos; i = text.find(pattern, i + 1)) count++;    std::cout << count << "\n";}
Cmain.c · 13 lines
#include <stdio.h>#include <string.h> static char text[5005]; int main(void) {    char pattern[16];    if (scanf("%5000s %10s", text, pattern) != 2) return 0;    int count = 0;    for (char* p = strstr(text, pattern); p != NULL; p = strstr(p + 1, pattern)) count++;    printf("%d\n", count);    return 0;}
Craykonmain.cray · 12 lines
text = Console.ReadLine().Trim();pattern = Console.ReadLine().Trim();m = pattern.Length;count = 0;for (i = 0; i + m <= text.Length; i++){    if (text.Substring(i, m) == pattern)    {        count++;    }}Console.WriteLine(count);