题目描述

首先给定六个指令，接下来按照以下的规则进行判断

1.只有一个字符串，直接与reset比较即可，如果可以匹配输出，否则unknown command

2.输入了两个字符串，首先匹配第一个字符串，如果匹配成功，看第二个，如果第二个匹配不成功，输出unknown command

3.输入两个字符串，首先匹配第一个字符串，如果第一个不成功，直接输出unknown command

4.输入了两个字符串，首先匹配第一个字符串，如果匹配成功，看第二个，如果第二个有唯一的正确匹配，输出对应命令，如果有多个则输出unknown command

样例解释

reset
reset board
board add
board delet
reboot backplane
backplane abort

这五个都是可以直接正常匹配成功的，所以直接输出他们对应的答案即可

reset what
board fault
where to add
no board at all
impossible
install first

知识点： 字符串，模拟

难度： 两星

解法

解法一：存储，模拟

思路分析：

我们可以直接把他们这几个字符串存到一个vector里面，然后我们每次分别比较前面一个和后面一个，最后判断有几个对应上，然后输出答案

C++代码实现：

#include <iostream>
#include <vector>
#include <cstring>
#include <unordered_map>
using namespace std;
string s, s1 = "", s2 = "";
// s为输入的字符串
vector<pair<string, string>> a;
unordered_map<string, string> mp;
// a为我们的前后字符串
// mp为我们对应的输出的答案

void init() {
    a.push_back({"reset", "board"});
    a.push_back({"board", "add"});
    a.push_back({"board", "delete"});
    a.push_back({"reboot", "backplane"});
    a.push_back({"backplane", "abort"});
    mp["reset board"] = "board fault";
    mp["board add"] = "where to add";
    mp["board delete"] = "no board at all";
    mp["reboot backplane"] = "impossible";
    mp["backplane abort"] = "install first";
}
// 初始化操作，把我们的前后的和我们的对应的输出的答案存储起来

void solve() {
    bool flag = false;
    for (auto &it : s) {
        if (it == ' ') {
            flag = true;
            continue;
        }
        flag ? s2 += it : s1 += it;
    }
    // 这个是判断什么时候存入s1，什么时候存入s2
    if (s2 == "") {
        string tmp = "reset";
        if (tmp.find(s1) == 0) {
            // 这个是判断我们是不是第一个匹配的位置是0
            cout << "reset what\n";
            return;
        }
        cout << "unknown command\n";
        return;
    }
    // 上面是对单指令进行的一个操作
    string tmp = "";
    int cnt = 0;
    for (auto &[u, v] : a) {
        if (u.find(s1) == 0) {
            if (v.find(s2) == 0) {
                tmp = u + " " + v;
                cnt++;
            }
        }
        // 如果两个都是匹配了成功，那么我们存储下来，然后次数+1
    }
    if (cnt == 1) {
        cout << mp[tmp] << "\n";
        return;
    }
    // 如果次数是一次直接输出，否则输出不知道
    cout << "unknown command\n";
    return;
}

signed main() {
    init();
    while(getline(cin, s)) {
        // 整行输入
        s1 = s2 = "";
        solve();
    }
    return 0;
}

时空复杂度分析

算法时空复杂度：

时间复杂度： $O(n)O(n)$

理由如下：因为find函数的时间复杂度平均是$O(n)O(n)$，然后我们有6个，所以我们最后的时间复杂度就是$O(n)O(n)$

空间复杂度： $O(n)O(n)$

理由如下：因为我们输入的字符串就是一个长度为$nn$的，所以我们的空间复杂度就是$O(n)O(n)$

本题的时空复杂度：

时间复杂度： $O(1)O(1)$

理由如下：因为我们的数据非常小，最后得到的就是一个常数的时间，所以无关紧要是$O(1)O(1)$

空间复杂度： $O(1)O(1)$

理由如下：因为我们的数据非常小，最后得到的就是一个常数的时间，所以无关紧要是$O(1)O(1)$

图解算法：

解法二：手写find函数

思路分析：

这里我们把find函数重新手写，其实我们只要比较我们输入的字符串是否可以匹配即可，其余的我们可以不用考虑

C++代码实现：

#include <cstring>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
string s, s1 = "", s2 = "";
// s为输入的字符串
vector<pair<string, string>> a;
unordered_map<string, string> mp;
// a为我们的前后字符串
// mp为我们对应的输出的答案

void init()
{
    a.push_back({ "reset", "board" });
    a.push_back({ "board", "add" });
    a.push_back({ "board", "delete" });
    a.push_back({ "reboot", "backplane" });
    a.push_back({ "backplane", "abort" });
    mp["reset board"] = "board fault";
    mp["board add"] = "where to add";
    mp["board delete"] = "no board at all";
    mp["reboot backplane"] = "impossible";
    mp["backplane abort"] = "install first";
}
// 初始化操作，把我们的前后的和我们的对应的输出的答案存储起来

bool cmp(string a, string b)
{
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i])
            return false;
    }
    return true;
}
// a为我们输入的字符串，b是我们的存入vector的

void solve()
{
    bool flag = false;
    for (auto& it : s) {
        if (it == ' ') {
            flag = true;
            continue;
        }
        flag ? s2 += it : s1 += it;
    }
    // 这个是判断什么时候存入s1，什么时候存入s2
    if (s2 == "") {
        string tmp = "reset";
        if (cmp(s1, tmp)) {
            // 这个是判断我们是不是第一个匹配的位置是0
            cout << "reset what\n";
            return;
        }
        cout << "unknown command\n";
        return;
    }
    // 上面是对单指令进行的一个操作
    string tmp = "";
    int cnt = 0;
    for (auto& [u, v] : a) {
        if (cmp(s1, u)) {
            if (cmp(s2, v)) {
                tmp = u + " " + v;
                cnt++;
            }
        }
        // 如果两个都是匹配了成功，那么我们存储下来，然后次数+1
    }
    if (cnt == 1) {
        cout << mp[tmp] << "\n";
        return;
    }
    // 如果次数是一次直接输出，否则输出不知道
    cout << "unknown command\n";
    return;
}

signed main()
{
    init();
    while (getline(cin, s)) {
        // 整行输入
        s1 = s2 = "";
        solve();
    }
    return 0;
}

时空复杂度分析

算法时空复杂度：

时间复杂度： $O(n)O(n)$

理由如下：首先其实我们的时间复杂度的瓶颈就是在于我们的for循环以及我们的匹配，这里我们手写的匹配就是我们每次判断的就是我们输入的字符串的长度，假设我们输入的字符串长度为n, 那么我们的时间复杂度就是$O(n)O(n)$

空间复杂度： $O(n)O(n)$

理由如下：因为我们输入的字符串就是一个长度为$nn$的，所以我们的空间复杂度就是$O(n)O(n)$

本题的时空复杂度：

时间复杂度： $O(1)O(1)$

理由如下：因为我们的数据非常小，最后得到的就是一个常数的时间，所以无关紧要是$O(1)O(1)$

空间复杂度： $O(1)O(1)$

理由如下：因为我们的数据非常小，最后得到的就是一个常数的时间，所以无关紧要是$O(1)O(1)$