【C++题解】统计子序列_c++子序列个数

$Part$ $1$ 读题

题目描述

$wgy$作为字符串属性的魔法师，有一件史诗级法宝——字符串$S$（字符串谁没有了 直接$string$ $S$这就好了）

下头男$why$作为$wgy$的粉丝，努力修炼，深入险境，只为获得和$wgy$类似的法宝，经过数十年的积累，下头男$why$获得了$n$个字符串，现在下头男$why$想知道，这$n$个字符串有多少个在$S$中出现。

请你帮他统计一下几个字符串$n$在$S$中出现，是指$n$为$S$的一个子序列。

输入格式

第一行：一个字符串$S$

第二行：一个正整数$n$

接下来$n$行，每行一个字符串$c[i]$

输出格式

一行一个整数表示答案

输入样例1

abcde
4
a
bb
acd
ace
1
2
3
4
5
6

输出样例1

3
1

输入样例2

babaaaa
5
abaaab
aaaaaaa
aa
aaaaaaa
ab
1
2
3
4
5
6
7

输出样例2

2
1

输入样例3

a
1
a
1
2
3

输出样例3

1
1

样例说明

对于样例$1$，$S$中出现的字符串为：$a$，$acd$，$ace$，共$3$个

数据范围与提示

对于$20\%$的数据：$|S|\le 50000$，$n\le 200$

对于$50\%$的数据：$|S|\le 50000$,$n\le 2000$

对于$100\%$的数据：$|S|\le 50000$，$n\le 5000$，$|c[i]|\le 50$

$Part$ $2$ 思路

看到题目，我们就能想到需要进行字符串比较，遍历字符串$s$，若遇到$c[1]$之后再对后面的进行判断，用计数器加上满足条件的个数，比较$n$与计数器，相等的时候就归零，个数加$1$，以此类推。

我们就得到了如下代码：

for(int i=0;i<n;i++){
    cin>>t; 
    lt=t.size();//lt：t的长度
    b=0;//求字符长度的计数器，每次循环开始记着归零
    for(int j=0;j<ls;j++){//ls：字符串s的长度
        if(s[j]==t[b])b++;//比较，两个字符相等就++
        if(b==lt){//归零及个数加1操作，记着要跳出循环
            b=0; 
            a++; 
            break;
    	}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

然后我们再加上定义、输入和输出就可以啦！

小tip：大家可以先根据思路，写一下代码哦！

$Part$ $3$ 代码

#include<bits/stdc++.h>
using namespace std;
string s,t; 
int n,a=0,b=0,ls,lt;
int main(){
    cin>>s>>n;
    ls=s.size();//ls：字符串s的长度
    for(int i=0;i<n;i++){
    	cin>>t; 
   		lt=t.size();//lt：t的长度
    	b=0;//求字符长度的计数器，每次循环开始记着归零
    	for(int j=0;j<ls;j++){
        	if(s[j]==t[b])b++;//比较，两个字符相等就++
        	if(b==lt){//归零及个数加1操作，记着要跳出循环
            	b=0; 
	            a++; 
	            break;
	    	}
		}
	}
    cout<<a;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

听完后，是不是觉得很简单呢？赶快自己去试一下吧！！！