(洛谷)P8835 [传智杯 #3 决赛] 子串

2023-12-16 05:41:00

[传智杯 #3 决赛] 子串

题目背景

disangan233 喜欢字符串,于是 disangan333 想让你找一些 disangan233 喜欢的串。

题目描述

在传智的开发课堂上,希望您开发一款文档处理软件。

给定 T T T 组询问,每次给定 2 2 2 个长度为 n , m n,m n,m 的只含英文字母的字符串 a , b a,b a,b,求 a a a b b b 中的出现次数,相同字符不区分大小写。注意 a a a b b b 中连续子序列。

对于所有数据, T ≤ 100 T\leq 100 T100 ∑ n ≤ ∑ m ≤ 1 0 3 \sum n\leq \sum m\leq 10^3 nm103。字符串仅由大小或者小写的英文字母组成。

输入格式

输入共 3 T + 1 3T+1 3T+1 行。

1 1 1 行输入 1 1 1 个正整数 T T T

接下来共 T T T 组输入,每组输入共 3 3 3 行。

1 1 1 行输入 2 2 2 个正整数 n , m n,m n,m

2 2 2 行输入一个长度为 n n n 的字符串 a a a

3 3 3 行输入一个长度为 m m m 的字符串 b b b

输出格式

输出共 T T T 行,第 i i i 行输出 1 1 1 个整数,表示询问 i i i 的答案。

样例 #1

样例输入 #1

5
3 10
abc
abcabcabca
2 10
aa
AAaAaaAaAa
5 5
AbCdE
eDcBa
5 5
abcde
ABCDE
3 10
aba
ABaBaAbaBA

样例输出 #1

3
9
0
1
4

提示

对于第一组输入,出现了 3 3 3 次,分别是 [abc]abcabcaabc[abc]abcaabcabc[abc]a

对于第二组输入,出现了 9 9 9 次,分别是 [Aa]AaaAaAaA[aA]aaAaAaAa[Aa]aAaAaAaA[aa]AaAaAaAa[aA]aAaAaAaa[Aa]AaAaAaaA[aA]aAaAaaA[aA]aAaAaaAa[Aa]

//  P8835 [传智杯 #3 决赛] 子串
#include <iostream>
#include <string>
using namespace std;

string a_A(string s) //小写转换
{
	for(int i=0;i<s.size();i++)
		if(s[i]>='A' && s[i]<='Z') s[i]+=32;
	return s;
}

string t1,t2;
int n,x,y,cnt;

int main()
{
	cin>>n;
	while(n--)
	{
		cnt = 0;  //因为多组数据测试  所以每组测试完要归0  
		cin>>x>>y>>t1>>t2;
		
		t1 = a_A(t1),t2 = a_A(t2);
		
		int len1 = t1.size(),len2 = t2.size();
		
		for(int i=0;i<len2;i++)
		{
			if(t2.substr(i,len1)==t1) cnt++;  // 字符串 截取函数  substr()    6666
		}	
		    cout<<cnt<<endl;
	}
	return 0;
}

/*
疑惑。。。。。   OK 解决
#include <iostream>
#include <string>
using namespace std;
int main()
{

string x = "ab12";

cout<<x.substr(2,2);

return 0;
}
*/

文章来源:https://blog.csdn.net/weixin_47830774/article/details/135026939
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。