題目描述

密碼要求:

1.長度超過8位

2.包括大小寫字母.數(shù)字.其它符號,以上四種至少三種

3.不能有相同長度超2的子串重復(fù)

說明:長度超過2的子串

輸入描述:

一組或多組長度超過2的子符串。每組占一行
輸出描述:
如果符合要求輸出：OK，否則輸出NG
輸入例子:
021Abc9000021Abc9Abc1021ABC9000021$bc9000
輸出例子:
OKNGNGOK這題本來難度不大，但是碰壁太多，有幾個經(jīng)驗教訓(xùn)記錄一下：
1.循環(huán)輸入處理時，輸入一行后就卡住不動無法再輸入，一般是在處理時出現(xiàn)死循環(huán)，需要單步定位死循環(huán)位置。
2.寫循環(huán)時要盡量考慮算法復(fù)雜度，開始一直由于耗時過長無法AC，調(diào)試發(fā)現(xiàn)第三個條件判斷時，雙層循環(huán)并在內(nèi)部還調(diào)用了泛型算法，處理過于復(fù)雜。
另外還有一個壞習(xí)慣：總喜歡把中間結(jié)果先緩存，再用range-for或迭代器統(tǒng)一處理，這樣無疑又會增加復(fù)雜度，能及時處理的就要盡快得出結(jié)果。
此題關(guān)鍵在于三個條件的判斷，第一個好說，第二個也相對簡單，難點在第三個，第三個問題抽象成一般問題之后其實就是：
判斷字符串中是否存在長度超過2的重復(fù)出現(xiàn)的子串？
如：“021Abc9Abc~00”，這串字符中“Abc“”出現(xiàn)了兩次，因此該種密碼不合格，條件3不滿足。
這個問題用容器來處理的思路是：將字符串從第一個字符開始，每三個字符劃分成子串（調(diào)用string::substr()，每次后移1個位置，因此劃分后的子串會有重疊），每次在子串后面查找是否有相同的子串（調(diào)用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;//后續(xù)字符串中查到了該子串，說明條件不滿足    } 該條件的判斷還可以衍生成更加一般性的問題，以后可能會用到：
統(tǒng)計字符串中重復(fù)出現(xiàn)的子串（子串長度超過2）個數(shù)，記錄其重復(fù)次數(shù)？
    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次就更新統(tǒng)計變量                repeatCnt++;                pos++;        }        if(repeatCnt>1){//出現(xiàn)重復(fù)，記錄重復(fù)的子串和重復(fù)次數(shù)                pair<string,int> e(str,repeatCnt);                map_substrs.insert(e);        }    }    for(auto e:map_substrs){        cout<<e.first<<"  "<<e.second<<endl;//重復(fù)的子串及重復(fù)次數(shù)    }    cout<<map_substrs.size()<<endl;//重復(fù)子串的個數(shù)
此題的完整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;        }    }}