HJ20 密码验证合格程序

题目描述

密码要求:

1.长度超过8位

2.包括大小写字母.数字.其它符号,以上四种至少三种

3.不能有长度大于2的包含公共元素的子串重复 （注：其他符号不含空格或换行）

示例

输入

021Abc9000

021Abc9Abc1

021ABC9000

021$bc9000

输出

OK

NG

NG

OK

思路

前两个条件简单，第三个条件，不能有长度>2的公共子串，这里我第一反应是校验是否有长度为3的子串、长度为4的子串……长度为n-1的子串，但是没什么办法。看了一眼题解才发现只考虑是否有长度为3的公共子串即可，而如果有长度大于3的公共子串时，必然是包含长度等于3的子串，所以只需要考虑这一种情况。

知识点：

1. 使用int pos = s.rfind(s.substr(i, 3));方法从后向前查找字符串

Code

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

bool check(string s) {
    int A = 0, a = 0, N = 0, Other = 0;
    int sz = s.size();
    for(int i = 0; i < sz; ++i) {
        bool flag = 0;
        if(s[i] >= 'A' && s[i] <= 'Z') {
            A = 1;
            flag = 1;
        }
        if(s[i] >= 'a' && s[i] <= 'z') {
            a = 1;
            flag = 1;
        }
        if(s[i] >= '0' && s[i] <= '9') {
            N = 1;
            flag = 1;
        }
        if(!flag && s[i] != ' ') {
            Other = 1;
        }
    }
    return A + a + N + Other >= 3;
}

int main() {

    freopen("00input.txt", "r", stdin);

    string s;
    while(getline(cin, s)) {
        if(s.length() <= 8 || !check(s)) {
            cout << "NG\n";
            continue;
        }
        int sz = s.size();
        bool flag = true;
        for(int i = 0; i + 2 < sz; ++i) {
            int pos = s.rfind(s.substr(i, 3));
            if(pos != i) {
                cout << "NG\n";
                flag = false;
                break;
            }
        }
        if(flag) {
            cout << "OK\n";
        }
    }
    return 0;
}