题解 | 密码验证合格程序

#include <iostream>
#include<regex>
using namespace std;
//难点就是判断字符串是否存在两个相同的独立子串，题目要求存在长度大于二，我们就只需要判断是否有长度为三的重复子串即可，因为更长的重复子串必然包括了长度为三的重复部分
//两种方法，第一种从头到尾遍历每个长度三的子串，然后和后续部分中的长度三的子串对比即可
//第二种是使用正则表达式，要注意匹配模式（注意 在C++中难以实现有重叠部分的相同子串的匹配，比如ABABAB中的ABA出现了两次，但是有重叠部分，难以用正则表达式匹配）

//判断是否至少三种字符
bool has3type(string line)
{
    int upper=0,lower=0,digit=0,other=0;
    //遍历line中的每一个字符，判断属于哪一种字符
    for(char it : line)
    {
        if(isupper(it))
            upper=1;
        else if(islower(it))
            lower=1;
        else if(isdigit(it))
            digit=1;
        else
            other=1;
    }
    if((upper+lower+digit+other)>=3)//存在至少三种类型字符
        return true;
    else
        return false;
}

//判断是否有重复子串
bool hassamesub(string line)
{   
    //方法一，遍历字符串，只需判断长度为三的子串，更长的重复子串必然包含了长度三的重复子串
    //子串最初起始位置为0，最后起始位置为size-6，每个子串都只用和后续部分比较即可
    // for(int i=0; i<=line.size()-6; i++)
    // {
    //     string sub1=line.substr(i,3);
    //     //和后续的所有子串比较，子串最初的起始位置为i+3，最后的起始位置为size-3
    //     for(int j=i+3; j<=line.size()-3; j++)
    //     {
    //         string sub2=line.substr(j,3);
    //         if(sub1==sub2)
    //             return true;//找到了重复子串
    //     }
    // }

    //方法二，正则表达式
    //.*匹配任意长度字符，(...)匹配连续三个字符记为组1，(.*\\1)匹配任意字符加上组一，末尾.* 匹配任意长度字符
    regex pattern(".*(...)(.*\\1).*");
    if(regex_search(line,pattern))
        return true;

    return false;//未找到重复子串
}

//判断是否为合格密码
bool isvalidpwd(string line)
{
    //判断是否长度不少于八位
    if(line.size()<8)
        return false;  
    //判断是否存在至少三种字符
    if(!has3type(line))
        return false;
    //判断是否存在独立的长度大于二的重复子串
    if(hassamesub(line))
        return false;
    return true;//符合所有要求
}

int main()
{
    string line;
    while(getline(cin,line))//依次处理每行
    {
        if(isvalidpwd(line))
            cout<<"OK"<<endl;
        else
            cout<<"NG"<<endl;
    }
}