题解 | 哈希冲突

import java.util.*;
import java.io.*;
import java.security.*;

public class Main {
    static class SHA256 {
        private static final long[] K = {
            0x428a2f98L, 0x71374491L, 0xb5c0fbcfL, 0xe9b5dba5L, 0x3956c25bL, 0x59f111f1L, 0x923f82a4L, 0xab1c5ed5L,
            0xd807aa98L, 0x12835b01L, 0x243185beL, 0x550c7dc3L, 0x72be5d74L, 0x80deb1feL, 0x9bdc06a7L, 0xc19bf174L,
            0xe49b69c1L, 0xefbe4786L, 0x0fc19dc6L, 0x240ca1ccL, 0x2de92c6fL, 0x4a7484aaL, 0x5cb0a9dcL, 0x76f988daL,
            0x983e5152L, 0xa831c66dL, 0xb00327c8L, 0xbf597fc7L, 0xc6e00bf3L, 0xd5a79147L, 0x06ca6351L, 0x14292967L,
            0x27b70a85L, 0x2e1b2138L, 0x4d2c6dfcL, 0x53380d13L, 0x650a7354L, 0x766a0abbL, 0x81c2c92eL, 0x92722c85L,
            0xa2bfe8a1L, 0xa81a664bL, 0xc24b8b70L, 0xc76c51a3L, 0xd192e819L, 0xd6990624L, 0xf40e3585L, 0x106aa070L,
            0x19a4c116L, 0x1e376c08L, 0x2748774cL, 0x34b0bcb5L, 0x391c0cb3L, 0x4ed8aa4aL, 0x5b9cca4fL, 0x682e6ff3L,
            0x748f82eeL, 0x78a5636fL, 0x84c87814L, 0x8cc70208L, 0x90befffaL, 0xa4506cebL, 0xbef9a3f7L, 0xc67178f2L
        };
        
        public static String hash(String input) {
            try {
                MessageDigest digest = MessageDigest.getInstance("SHA-256");
                byte[] hash = digest.digest(input.getBytes("UTF-8"));
                StringBuilder hexString = new StringBuilder();
                for (byte b : hash) {
                    String hex = Integer.toHexString(0xff & b);
                    if (hex.length() == 1) hexString.append('0');
                    hexString.append(hex);
                }
                return hexString.toString();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
    }
    
    static int encLen;
    static String encKey;
    
    static String H(String str) {
        String combined = encKey + str;
        return SHA256.hash(combined).substring(0, encLen);
    }
    
    static class Pair<T, U> {
        T first;
        U second;
        
        Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }
    }
    
    static Pair<String, String> solve() {
        // 在此处补全代码
        dfs(new HashMap(), "", encLen);
        return pair;
    }
    static Pair pair;
    static boolean find = false;

    static void dfs(Map map, String s, int encLen) {
        if (find) return;
        if (encLen == 0) {
            String hash = H(s);
            if (map.containsKey(hash)) {
                find = true;
                pair = new Pair(s, map.get(hash));
            }
            map.put(hash, s);
            return;
        }
    
        for (char c = 'a'; c <= 'z' && !find; c++) {
            dfs(map, s + c, encLen - 1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        encLen = scanner.nextInt();
        encKey = scanner.next();
        
        Pair<String, String> result = solve();
        System.out.println(result.first + " " + result.second);
        
        scanner.close();
    }
}