ccf:201409-03 字符串匹配 （技巧总结 + 满分题解 + 解题思路）

本题主要考察字符串的相关操作

//字符串的查找
//1. 方法一：find()函数————时间复杂度为两个字符串长度乘积
string a = "abcde";
string b = "ab";
cout << a.find(b) //输出零，字串的第一个下标位置

//2. 方法二：strstr()函数————时间复杂度为线性时间复杂度，和kmp时间复杂度差不多
char father[N];
char son[N];

cin >> father;
cin >> son;
char * res = strstr(father, son); //在老爹里找儿子

if(res == NULL) //找不到返回null
	printf("不能找到");
else //若是找到，则返回字串在主串中第一次出现的位置及以后的字符串；strstr(abcdef, bc)结果尾bcdef
	printf("%s", res);

//字符串大小写转换
//使用transform函数
#include 
string a;
transform(a.begin(), a.end(),a.begin(),::tolower); //toupper是将字符变为大写

数据范围不大，利用find函数寻找时间复杂度n*2，不会超时大小写敏感则直接find，大小写不敏感则将字串和查询串统一为大写或小写后再find查找子串是否存在
代码实现

#include 
#include 
#include 

using namespace std;

string s;
bool flag;
int n;

//strstr和kmp效率差不多，0(n);
int main()
{
    cin >> s;
    cin >> flag;
    cin >> n;
    
    if (!flag) 
    {
        transform(s.begin(),s.end(),s.begin(),::tolower);
    }
    while (n --)
    {
        string a;
        string res;
        cin >> a;
        res = a;
        if (!flag) transform(a.begin(), a.end(), a.begin(), ::tolower);
        if(a.find(s) != -1) //find是区分大小写的,若找到则返回字串首字母下标位置，时间复杂度0(n * m)
        {
            cout << res << endl;
        }
        
    }
    return 0;
}