题目描述
给出一个字符串和多行文字,在这些文字中找到字符串出现的那些行。
你的程序还需支持大小写敏感选项:当选项打开时,表示同一个字母的大写和小写看作不同的字符;当选项关闭时,表示同一个字母的大写和小写看作相同的字符。
输入格式
输入的第一行包含一个字符串 S,由大小写英文字母组成。
第二行包含一个数字,表示大小写敏感的选项,当数字为 0 时表示大小写不敏感,当数字为 1 时表示大小写敏感。
第三行包含一个整数 n,表示给出的文字的行数。
接下来 n 行,每行包含一个字符串,字符串由大小写英文字母组成,不含空格和其他字符。
输出格式
输出多行,每行包含一个字符串,按出现的顺序依次给出那些包含了字符串 S 的行。
数据范围
$1≤n≤100$,
每个字符串的长度不超过 100。
输入样例:
Hello
1
5
HelloWorld
HiHiHelloHiHi
GrepIsAGreatTool
HELLO
HELLOisNOTHello
输出样例:
HelloWorld
HiHiHelloHiHi
HELLOisNOTHello
样例解释
在上面的样例中,第四个字符串虽然也是 Hello,但是大小写不正确。
如果将输入的第二行改为 0,则第四个字符串应该输出。
思路
这题……直接暴力就行了
而且……这个暴力枚举C++里面还有一个函数:
就是string里的a.find(s)函数,这个函数是返回原串在当前串第一次出现的位置
如果找不到会返回-1,此函数的时间复杂度是O(nm)的
如果,只是如果,数据范围较大的话我们可以用kmp来做,这种做法可以吧时间复杂度做成$O(n)$的
另外C++里还有一种函数,就是strstr函数
代码$O(n^2)$
#include<iostream>
using namespace std;
const int N=110;
string get(string str)
{
string res;
for(auto c:str)//这是C++11包含一种新的for循环,称为基于范围的for循环,可以简化对数组元素的遍历
res+=tolower(c);
return res;
}
int main()
{
string s;
cin>>s;
int n;
bool type;
cin>>type>>n;
while(n--)
{
string str;
cin>>str;
if(type && str.find(s)!=-1) cout<<str<<endl;
else if(!type&&get(str).find(get(s))!=-1) cout<<str<<endl;//注意两个字符串都要变成小写
}
return 0;
}