可重叠子串 (Ver. I)

叶茂林

发布于 2023-07-30 11:46:09

1550

发布于 2023-07-30 11:46:09

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

题目描述

给定一个字符串（模式串）和一些待查找的字符串，求每个待查找字符串在模式串中出现的次数（可重叠）

输入

第一行输入t，表示有t组测试数据

每一组测试数据包含多行：

每一组的第一行包括一个字符串P，长度不超过105，且非空串

每一组的第二行包括一个整数N，代表待查找的字符串数量 (1 <= N <= 5)

每一组接下来的N行，每一行包括一个待查找的字符串，其长度不超过50，且非空串

输出

对于每组测试数据，

输出每个待查找字符串出现的次数，

具体输出见样例

输入样例1?

2 aabbcc 3 aa bb cc ababab 1 aba

输出样例1

aa:1 bb:1 cc:1 aba:2

思路分析

直接暴力求解，对于每一个待测试的子串，用find函数去找子串首次输出的位置，然后计数，并记录下位置，然后继续在该位置之后的字符串继续找子串出现的位置，然后计数，记录新的位置，以此类推，直到找不到了。跳出循环。

AC代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--){
        string master;
        int N;
        cin>>master>>N;
        while(N--){
            string test;
            cin>>test;
            int times=0,pos=0;
            while(master.find(test,pos)!=string::npos){
                times++;
                pos=master.find(test,pos);
                pos++;
            }
            cout<<test<<':'<<times<<endl;
        }
    }
}

本文参与?腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-10-19，如有侵权请联系 cloudcommunity@tencent.com 删除

int