2 道题

1. 请写一个字符串协议解析的实现，如 a=b&c=d& -> map[a]=b, map[c]=d.
   要求尽量保持对异常的兼容如 &&&===&a=b&
   a=bb&cc=dd&cc=

2. 请写一个在字符串中寻找子串第一个位置的实现，并给出相应复杂度

• 字符串长度为n, 字串长度m

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cassert>
#include <map>

using namespace std;

// 4-16 20:25 -> 50

/**
 1. 请写一个字符串协议解析的实现，如 a=b&c=d& -> map[a]=b, map[c]=d.
 要求尽量保持对异常的兼容如 &&&===&a=b&
 a=bb&cc=dd&cc=
 */
bool parse_uri_params(const std::string& str, std::map<std::string,std::string>& res){
    res.clear();
    std::string key = "";
    std::string value = "";
    bool now_is_key = true;
    for (int i=0;i<str.length();i++){
        if (str[i] == '='){
            now_is_key = false;
        }else if (str[i]=='&'){
            now_is_key=true;
            if (key.length()>0) res[key] = value;
            key.clear();
            value.clear();
        }else {
            if (now_is_key) key.push_back(str[i]);
            else value.push_back(str[i]);
        }
    }
    if (key.length()>0 && value.length() > 0) {
        res[key] = value;
    }
}

/**
 *  2. 请写一个在字符串中寻找子串第一个位置的实现，并给出相应复杂度
 * 字符串长度为n, 字串长度m
 * 时间复杂度：O(m+n)
 * 空间 O(n)
 */
// 计算匹配串的 next 数组 O(m)
void getNext(const string &sub, vector<int> &next) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < (int) sub.length() - 1) {
        if (j == -1 || sub[i] == sub[j]) {
            i++;
            j++;
            if (sub[i] == sub[j]) {
                next[i] = next[j];
            } else {
                next[i] = j;
            }
        } else {
            j = next[j]; //失配时，模式串向右移动
        }
    }
}
// KMP 匹配字符串，返回匹配的位置，失败返回-1
int KMP(string &str, string &sub, int start_pos = 0) {
    int i = start_pos, j = 0;
    vector<int> next;
    next.reserve(sub.length() + 1);
    getNext(sub, next);
    while (i < (int) str.length() && j < (int) sub.length()) {
        if (j == -1 || str[i] == sub[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    //返回开始匹配到的主串位置
    if (j == (int) sub.length()) {
        return i - j;
    }
    return -1;
}
int main() {
    // case1
    {
        string str = "abc123";
        string sub = "123";
        int pos = KMP(str, sub, 0);
        std::cout << pos << " " << (pos < 0 ? "not found" : "found") << endl;
    }
    {
        string str = "abc123";
        string sub = "22";
        int pos = KMP(str, sub, 0);
        std::cout << pos << " " << (pos < 0 ? "not found" : "found") << endl;
    }
    {
        //string str= "&&&===&a=b&";
        string str= "a=bb&cc=dd&cc=";
        map<string,string> out;
         parse_uri_params(str, out);
         for(auto s:out){
             cout<< s.first << "="<<  s.second<<endl;
         }
    }


    return 0;
}