201803-3 CCF URL映射 满分题解

问题描述

URL映射原题链接

解题思路

规则的路径和名字用空格间隔，则可以通过cin分别读取和存储
可以采用结构体存储每一条规则
再将url每一条读入并解析匹配，若匹配成功，则输出答案，否则404

实现技巧

匹配的实现，可以采用双指针，以/为分隔，取出字符串
对字符串的类型进行判断str/int/path/常量
将答案存储在vector< string > 中
匹配过程中，出现不匹配则清空vector，返回
所以结果大小为零，则匹配失败
初始化结果大小为1
所以结果大小为1，则匹配成功，但无参
所以结果大小为零，则匹配成功，并有参

代码实现

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

using namespace std;

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

//判断该字符串是否是一串数字，并返回这串数字
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 ++; // 去除前缀零
    res = num.substr(k);
    return res;
}

//判断url是否与规则匹配，并返回参数值
vector <string> check(string & path, string & query)
{
    
    //res.size() == 0 表示不匹配
    //res.size() == 1 表示匹配，但无参
    //res.size() > 1 表示匹配，并有参
    vector <string> res(1); //申请一个空间的数组
    int i, j;
    for (i = 1, j = 1; i < path.size() && j < query.size(); )
    {
    
        //需要双指针代替i, j向后走，因为后面path处需要“回溯”
        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;
        }
    }
    //这句语句写的很巧妙
    //判断了两个条件
    //首先规则和url末尾必须同时等于/或同时不等于/
    //其次规则和url都应同时走到最后，排除了部分匹配的情况
    if (i - path.size() != j - query.size())
    {
    
        res.clear();
        return res;
    }
    return res;    
}

void work(string & str, int n) //加引用可以减少复制，提高速度
{
    
    for (int i = 0; i < n; i ++)
    {
    
        auto res = check(url[i].path, str);
        
        //匹配成功，则输出参数并返回
        if (res.size())
        {
    
            cout << url[i].name;
            for (int j = 1; j < res.size(); j ++) //j从1开始，res[0]是判断是否匹配成功的标志
            {
    
                cout << " " << res[j];
            }
            cout << endl;
            return ; 
        }
    }
    //此时说明并未匹配成功
    puts("404");
}
int main()
{
    
    int n, m;
    cin >> n >> m;
    
    //因为用空格分隔，所以可以直接用cin读取，分开存储
    for (int i = 0; i < n; i ++) cin >> url[i].path >> url[i].name;
    
    string str;
    for (int i = 0; i < m; i ++)
    {
    
        //将每一个询问读取并解析
        cin >> str;
        work(str, n);
    }
    return 0;
}