201803-3 Full Score solution of CCF URL mapping

Problem description

URL Map the original question link

Their thinking

Regular paths and names are separated by spaces , You can use the cin Read and store separately
May adopt Structure storage Every rule
then url Each entry is read and parsed matching , If the match is successful , Then output the answer , otherwise 404

Implementation skills

Matching implementation , Double pointers can be used , With / For division , Take out the string
Judge the type of string str/int/path/ Constant
Store answers in vector< string > in
During the matching process , If there is a mismatch, clear vector, return
therefore The result size is zero , The match fails
The initialization result size is 1
therefore The result size is 1, Then the match is successful , But no reference
therefore The result size is zero , Then the match is successful , And have reference

Code implementation

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

using namespace std;

struct Url
{
    
    string path;
    string name;
}url[110];

// Judge whether the string is a string of numbers , And return this string of numbers 
string check_num(string num)
{
    
    string res;
    for (int i = 0; i < num.size(); i ++)
    {
    
        if (num[i] >= '0' && num[i] <= '9') continue;
        else
        {
    
            res.clear();
            return res;
        }
    }
    int k = 0;
    while (k < num.size() - 1 && num[k] == '0') k ++; //  Remove the prefix zero 
    res = num.substr(k);
    return res;
}

// Judge url Whether it matches the rule , And return the parameter value 
vector <string> check(string & path, string & query)
{
    
    //res.size() == 0  Indicates a mismatch 
    //res.size() == 1  Represents a match , But no reference 
    //res.size() > 1  Represents a match , And have reference 
    vector <string> res(1); // Apply for an array of spaces 
    int i, j;
    for (i = 1, j = 1; i < path.size() && j < query.size(); )
    {
    
        // Need double pointer instead i, j Go back to , Because the back path We need “ to flash back ”
        int u = i + 1, v = j + 1;
        while (u < path.size() && path[u] != '/') u ++;
        while (v < query.size() && query[v] != '/') v ++;
        
        string type = path.substr(i, u - i);
        string value = query.substr(j, v - j);
        
        if (type == "<str>")
        {
    
            res.push_back(value);
            i = u + 1;
            j = v + 1;
        }
        else if (type == "<int>")
        {
    
            auto num = check_num(value);
            if (num.size()) 
            {
    
                res.push_back(num);
                i = u + 1;
                j = v + 1;
            }
            else
            {
    
                res.clear();
                return res;
            }
        }
        else if (type == "<path>")
        {
    
            res.push_back(query.substr(j));
            return res;
        }
        else if (type != value)
        {
    
            res.clear();
            return res;
        }
        else
        {
    
            i = u + 1;
            j = v + 1;
        }
    }
    // This sentence is cleverly written 
    // Two conditions are judged 
    // First rule and url The end must be equal to / Or not equal to /
    // Secondly, rules and url Should go to the end at the same time , Excluding partial matching 
    if (i - path.size() != j - query.size())
    {
    
        res.clear();
        return res;
    }
    return res;    
}

void work(string & str, int n) // Adding references can reduce replication , Increase speed 
{
    
    for (int i = 0; i < n; i ++)
    {
    
        auto res = check(url[i].path, str);
        
        // The match is successful , Then output parameters and return 
        if (res.size())
        {
    
            cout << url[i].name;
            for (int j = 1; j < res.size(); j ++) //j from 1 Start ,res[0] It is a sign to judge whether the match is successful 
            {
    
                cout << " " << res[j];
            }
            cout << endl;
            return ; 
        }
    }
    // At this time, the description does not match successfully 
    puts("404");
}
int main()
{
    
    int n, m;
    cin >> n >> m;
    
    // Because separated by spaces , So you can use it directly cin Read , Separate storage 
    for (int i = 0; i < n; i ++) cin >> url[i].path >> url[i].name;
    
    string str;
    for (int i = 0; i < m; i ++)
    {
    
        // Read and parse each query 
        cin >> str;
        work(str, n);
    }
    return 0;
}