查找字符串P0030

统计重叠出现次数

第一行给出文本 text，第二行给出要找的串 pattern。
输出 pattern 在 text 中出现的次数。
出现的位置互相重叠也分别计数。
例如 "aa" 在 "aaaa" 中从第 0、1、2 个位置开始，共出现 3 次。
如果 pattern 比 text 长，答案为 0。

输入: text 为小写字母，长度 1 到 5,000。
pattern 为小写字母，长度 1 到 10
输出: 出现次数

样例 1 · stdin

aaaa
aa

stdout

样例 2 · stdin

abababa
aba

stdout

main.py 编程语言运行版本

输入(stdin)

运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。

$ 就绪

请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。

其他语言怎么写？查看各语言题解 · 8 种语言题解

内置的“出现几次”函数是不重叠计数的：Python text.count("aa") 对 "aaaa" 得到 2。
要计入重叠，就从找到位置的下一格（+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)（返回指向匹配处的指针）。
Craykon 的 查找位置 不接受起始位置，所以在每个位置用 text.截取(i, m) == pattern 比较。
陷阱：找到后跳过整个模式长度（+m）会漏掉重叠，和内置 count 一样。

Pythonmain.py · 8 行

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 行

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 行

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 行

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 行

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 行

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

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

text = 控制台.读行().去空白();pattern = 控制台.读行().去空白();m = pattern.长度;count = 0;循环 (i = 0; i + m <= text.长度; i++){    如果 (text.截取(i, m) == pattern)    {        count++;    }}控制台.输出(count);