华为OJ-密码验证合格程序-牛客网

密码要求:
1.长度超过8位
2.包括大小写字母.数字.其它符号,以上四种至少三种
3.不能有相同长度超2的子串重复
说明:长度超过2的子串

输入描述:
一组或多组长度超过2的子符串。每组占一行

输出描述:
如果符合要求输出：OK，否则输出NG

示例1
输入

1 021Abc9000
2 021Abc9Abc1
3 021ABC9000
4 021$bc9000

输出

1 OK
2 NG
3 NG
4 OK

求解思路：按照要求，分别建立三个函数 check_lengh, check_char_kinds和check_substr_repeat。前两个函数难度不大，对于判断字符串内是否存在重复长度超二的子串，有两种解法：

1. 暴力搜索：从下标开始搜索，取出长度为3的子字符串，然后利用std::string.find()进行查找；

2. 后缀数组方法：将字符串的子串 [i,n)存入vector容器suffix中，调用<algorithm>中的sort对子串按照字典序排列，遍历相邻子串suffix[i]与suffix[i+1]，求出其相同的字符数目，如果数目>2，即表示存在重复子串；

关于后缀数组方法的详细介绍及应用，可参考文章 http://www.cnblogs.com/biyeymyhjob/archive/2012/08/15/2639572.html

编写的AC代码如下：

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 bool check_length(const string &password){
 9     return password.size() > 8;
10 }
11 
12 bool check_char_kinds(const string & password){
13     int digit{0}, lowercase{0},uppercase{0},others{0};
14     for(int i = 0; i < password.size();++i){
15         if(isdigit(password[i])){
16             digit = 1;
17             continue;
18         }else if(islower(password[i])){
19             lowercase = 1;
20             continue;
21         }else if(isupper(password[i])){
22             uppercase = 1;
23             continue;
24         }
25         else{
26             others = 1;
27             continue;
28         }
29     }
30     return digit+lowercase+uppercase+others >= 3? true:false;
31 }
32 
33 bool check_substr_repeat_1(const string & password){
34     // simple search and match
35     for(int i = 0; i < password.size() - 3;++i){
36         string str1 = password.substr(i, 3);
37         if(password.find(str1,i+1) != string::npos)
38             return false;
39     }
40     return true;
41 
42 }
43 bool check_substr_repeat_2(const string & password){
44     // 后缀数组方法
45     vector<string> suffix(password.size());
46     for(int i = 0; i < password.size();++i){
47         suffix[i] = password.substr(i);
48     }
49     sort(suffix.begin(), suffix.end());
50     for(int i = 0; i < suffix.size()-1; ++i){
51         int len = 0;
52         int max_len = max(suffix[i].size(), suffix[i+1].size());
53         int j = 0;
54         while(j< max_len && suffix[i][j]== suffix[i+1][j]){
55             ++len;
56             ++j;
57             if(len > 2) return false;
58         }
59     }
60     return true;
61 }
62 
63 int main() {
64     ios::sync_with_stdio(false);
65     string line;
66     while(cin>> line){
67         if(check_length(line) && check_char_kinds(line) && check_substr_repeat_2(line))
68             cout <<"OK"<<endl;
69         else
70             cout <<"NG"<<endl;
71     }
72     return 0;
73 }