VIRTUALS

the virtual labs for the virtuals

0%

HJ20. 密码验证合格程序

Posted on Edited on In , , ,

摘要：
考察字符串处理，巧用位运算记录字符种类。

题目

描述
密码要求:

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

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

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

示例1

输入：

  • $021Abc9000$
  • $021Abc9Abc1$
  • $021ABC9000$
  • $021(bc9000$

输出：

  • $OK$
  • $NG$
  • $NG$
  • $OK$

字符串处理 + 位运算

我们根据题意依次判断几种不符合要求的条件即可。
关键在于判断子串的重复性，题目指出长度大于 $2$ 的子串不能重复，那么从长度为 $3$ 开始判断子串的重复性，如果无重复那么长度大于 $3$ 的子串也一定无重复。

简单证明：
假设长度为 $3$ 的子串经判断无重复，且长度大于 $3$ 的子串存在重复。那么因为长度大于 $3$ 的子串存在长度为 $3$ 的子串且重复，与假设相矛盾。
故假设不成立。
得证。

另外，在判断字符种类的时候，可以使用位运算辅助判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
 * author: etoa
 * 2021-06-06
 */
#include<bits/stdc++.h>

using namespace std;


inline bool SubStringDetermine(string s)
{
    unordered_map<string, int> hash;
    // i : length of sub string
    //for (int len = 3; len < s.size() - 1; len++)
    int len = 3;
    {
        for (int i = 0; i < s.size() - len + 1; i++)
        {
            string sub = s.substr(i, len);
            hash[sub] = hash[sub] + 1;
            if (hash[sub] > 1) 
                return false;
        }
    }
    return true;
}

inline int lowbit(int x)
{
    return x & (-x);
}

inline bool TypeDetermine(string s)
{
    int cnt = 0;
    for (auto c : s)
    {
        if (isupper(c))
            cnt |= 1;
        else if (islower(c))
            cnt |= (1 << 1);
        else if (isdigit(c))
            cnt |= (1 << 2);
        else 
            cnt |= (1 << 3);
    }
    // count 1
    int type = 0;
    for (; cnt; cnt -= (lowbit(cnt)))
        type++;
    return type >= 3;
}

inline bool SizeDetermine(string s)
{
    return s.size() > 8;
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    string s;
    for (;getline(cin, s);)
    {
        if (SizeDetermine(s) && TypeDetermine(s) && SubStringDetermine(s)) 
            cout << "OK" << endl;
        else 
            cout << "NG" << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
 * author: etoa
 * 2021-08-19 21:20:54
 */
import java.util.*;

public class Main {
    
    private static boolean substringDetermine(String s) {
        int n = s.length();
        int len = 3;
        Set<String> set = new HashSet<>();
        for (int i = 0; i <= n - len; i++) {
            String sub = s.substring(i, i + len);
            if (set.contains(sub)) return false;
            set.add(sub);
        }
        return true;
    }
    
    private static int lowbit(int x) {
        return x & -x;
    }
    
    private static boolean typeDetermine(String s) {
        int cnt = 0;
        for (int i = 0, n = s.length(); i < n; i++) {
            char c = s.charAt(i);
            if (Character.isUpperCase(c)) cnt |= 1;
            else if (Character.isLowerCase(c)) cnt |= 1 << 1;
            else if (Character.isDigit(c)) cnt |= 1 << 2;
            else cnt |= 1 << 3;
        }
        int type = 0;
        for (; cnt != 0; cnt -= lowbit(cnt)) ++type;
        return type >= 3;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s;
        for (; in.hasNext();) {
            s = in.nextLine();
            if (s.length() <= 8 || !typeDetermine(s) || !substringDetermine(s)) {
                System.out.println("NG");
            } else {
                System.out.println("OK");
            }
        }
    }
}

原题链接： HJ20. 密码验证合格程序