HJ20.密码验证合格程序

#include <iostream>
#include <string>
#include <unordered_set>

const std::string OK = "OK";
const std::string NG = "NG";

bool check1(const std::string& s) {
    return s.length() > 8;
}

bool check2(const std::string& s) {
    int type[4] = {0, 0, 0, 0};
    for (auto& i : s) {
        if (i == ' ' || i == '\n') {
            return false;
        }
        if (i >= 'A' && i <= 'Z') {
            type[0] = 1;
        }else if (i >= 'a' && i <= 'z') {
            type[1] = 1;
        }else if (i >= '0' && i <= '9') {
            type[2] = 1;
        }else {
            type[3] = 1;
        }
    }
    if (type[0] + type[1] + type[2] + type[3] < 3) {
        return false;
    }
    return true;
}

bool check3(const std::string& s) {
    std::unordered_set<std::string> sets;
    std::string tmp;
    for (int i = 0; i < s.length() - 2; ++i) {
        tmp = s.substr(i, 3);
        if (sets.find(tmp) == sets.end()) {
            sets.insert(tmp);
        }else {
            return false;
        }
    }
    return true;
}

int main() {
    std::string in;
    while (getline(std::cin, in)) {
        if (check1(in) && check2(in) && check3(in)) {
            std::cout << OK << '\n';
        }else {
            std::cout << NG << '\n';
        }
    }
    return 0;
}

解题思路：

难点1：题目本身，实在没搞清楚“3.不能有长度大于2的不含公共元素的子串重复 （注：其他符号不含空格或换行）”这句话的意思，什么叫“不含公共元素”是什么意思？最后是按照不含长度大于2的重复子串来做的；

难点2：重复子串的存在性判断。需要注意的是，这里只是判断有没有，并不是找出来，另外重复子串的长度是大于2，意味着我们只需要看长度为3的子串即可（如果有长度为4或者以上的子字符串，必然满足长度为3的重复子串存在！”；

难点3：如何快速找到子串吧，一种方式就是两层循环嵌套查找，时间复杂度比较高，题目没有对空间做限制，可以想到使用set快速查找，时间复杂度为O(n)，相当于用空间换时间了；

难点4：密码中总共有几种字符类型，还是字典的思想，这里简单用数组来实现；