华为机试在线训练-牛客网（12）密码验证合格程序

题目描述

密码要求:

1.长度超过8位

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

3.不能有相同长度超2的子串重复

说明:长度超过2的子串

输入描述:

一组或多组长度超过2的子符串。每组占一行
输出描述:
如果符合要求输出：OK，否则输出NG
输入例子:
021Abc9000021Abc9Abc1021ABC9000021$bc9000
输出例子:
OKNGNGOK这题本来难度不大，但是碰壁太多，有几个经验教训记录一下：
1.循环输入处理时，输入一行后就卡住不动无法再输入，一般是在处理时出现死循环，需要单步定位死循环位置。
2.写循环时要尽量考虑算法复杂度，开始一直由于耗时过长无法AC，调试发现第三个条件判断时，双层循环并在内部还调用了泛型算法，处理过于复杂。
另外还有一个坏习惯：总喜欢把中间结果先缓存，再用range-for或迭代器统一处理，这样无疑又会增加复杂度，能及时处理的就要尽快得出结果。
此题关键在于三个条件的判断，第一个好说，第二个也相对简单，难点在第三个，第三个问题抽象成一般问题之后其实就是：
判断字符串中是否存在长度超过2的重复出现的子串？
如：“021Abc9Abc~00”，这串字符中“Abc“”出现了两次，因此该种密码不合格，条件3不满足。
这个问题用容器来处理的思路是：将字符串从第一个字符开始，每三个字符划分成子串（调用string::substr()，每次后移1个位置，因此划分后的子串会有重叠），每次在子串后面查找是否有相同的子串（调用string::find()），代码如下：
    //条件3    string subStr;    for(unsigned int i=0;i<passWord.size()-3;i++){        subStr=password.substr(i,3);        if(password.find(subStr,i+3)!=string::npos)            return false;//后续字符串中查到了该子串，说明条件不满足    } 该条件的判断还可以衍生成更加一般性的问题，以后可能会用到：
统计字符串中重复出现的子串（子串长度超过2）个数，记录其重复次数？
    map<string,int> map_substrs;    string inStr;    cin>>inStr;    for(unsigned int i=0;i<inStr.size()-3;i++){//子串按三个字符一划分        string str=inStr.substr(i,3);        int repeatCnt=0;        unsigned int pos=0;        while((pos=inStr.find(str,pos))!=string::npos){//在字符串指定位置查找子串，查找位置每次后移1位，查到1次就更新统计变量                repeatCnt++;                pos++;        }        if(repeatCnt>1){//出现重复，记录重复的子串和重复次数                pair<string,int> e(str,repeatCnt);                map_substrs.insert(e);        }    }    for(auto e:map_substrs){        cout<<e.first<<"  "<<e.second<<endl;//重复的子串及重复次数    }    cout<<map_substrs.size()<<endl;//重复子串的个数
此题的完整AC代码如下：
#include <iostream>#include <vector>#include <string>using namespace std;bool judgePassword(string password){    //条件1    if(password.size()<=8)        return false;    //条件2    vector<int> flag={0,0,0,0};    for(auto c:password){        if(c>='a'&&c<='z'){            flag[0]=1;        }        else if(c>='A'&&c<='Z'){            flag[1]=1;        }        else if(c>='0'&&c<='9'){            flag[2]=1;        }        else{            flag[3]=1;        }    }    if(flag[0]+flag[1]+flag[2]+flag[3]<3)        return false;    //条件3    string subStr;    for(unsigned int i=0;i<password.size()-3;i++){        subStr=password.substr(i,3);        if(password.find(subStr,i+3)!=string::npos)            return false;    }    return true;} int main(){    string inStr;    while(getline(cin,inStr)){        if(judgePassword(inStr)==false){            cout<<"NG"<<endl;        }        else{            cout<<"OK"<<endl;        }    }}