CCF string matching (Full Score code + problem solving ideas + skill summary) March 3, 2014

Skill summary

This topic mainly examines the string related operations

// String lookup 
//1.  Method 1 ：find() function ———— The time complexity is the product of two string lengths 
string a = "abcde";
string b = "ab";
cout << a.find(b) // Output Zero , The first subscript position of the string 

//2.  Method 2 ：strstr() function ———— The time complexity is linear , and kmp Time complexity is almost 
char father[N];
char son[N];

cin >> father;
cin >> son;
char * res = strstr(father, son); // Look for your son in your father 

if(res == NULL) // No return found null
	printf(" Can't find ");
else // If you find , Returns the position of the first occurrence of the string in the main string and the subsequent string ;strstr(abcdef, bc) Result tail bcdef
	printf("%s", res);

// String case conversion 
// Use transform function 
#include <algorithm>
string a;
transform(a.begin(), a.end(),a.begin(),::tolower); //toupper Is to make characters uppercase 

Title Description

Their thinking

• The data range is small , utilize find Function search time complexity n*2, No timeout
• Case sensitive is direct find, Case insensitive, the string and query string are unified into upper case or lower case, and then find Find whether the substring exists

Code implementation

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

string s;
bool flag;
int n;

//strstr and kmp Almost efficient ,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 It's case sensitive , If found, the initial subscript position of the string will be returned , Time complexity 0(n * m)
        {
    
            cout << res << endl;
        }
        
    }
    return 0;
}