题解 | #密码验证合格程序#
密码验证合格程序
https://www.nowcoder.com/practice/184edec193864f0985ad2684fbc86841
基于KMP模式匹配的算法（check_3），另：在本题的数据量下，可能hash会更好一点
#include <bits/stdc++.h>
using namespace std;
bool match(string s,string p,int next[]){
if(s.length()>=3){
for(int i=0; i< s.length()-3; ++i){
string t= s.substr(i,3);
if(t==p)
return true;
for(int j= 0; j< 3; ++j)
if(t[j]!=p[j]){
i+= j- next[j]-1;
break;
}
}
}
return false;
}
bool KMPstr(string s){
string p,front,behind;
int next[3]={-1,0,0};
for(int i= 0;i< s.length()-3; ++i){
p= s.substr(i,3);
front= s.substr(0,i);
behind= s.substr(i+3);
if(p[0]==p[1])
next[3]=1;
else
next[3]=0;
if(match(front,p,next) || match(behind,p,next))
return true;
}
return false;
}
bool len(string s){
return s.length()>8;
}
bool kind(string s){
int a=0,b=0,c=0,d=0;
for(int i =0; i<s.length(); ++i){
if(s[i]-'a'>=0 && s[i]-'a'<=26)
a=1;
else if(s[i]-'A'>=0 && s[i]-'A'<=26)
b=1;
else if(s[i]-'0'>=0 && s[i]-'0'<=9)
c=1;
else if(s[i]!= ' ' && s[i]!= '\n')
d=1;
}
if(a+ b+ c+ d< 3)
return false;
return true;
}
int main(){
string s;
while(getline(cin, s)){
if(!len(s) || !kind(s) || KMPstr(s)){
cout<< "NG"<< endl;
continue;
}
cout<< "OK"<< endl;
}
}
