Java字符串哈希实现异常：子串排序不符合预期求助

核心问题分析 #

你的代码存在两个关键错误，导致输出不符合预期：

1. 子串分割逻辑错误
   原代码使用滑动窗口方式截取子串（步长为1），但需求要求将字符串从左至右分割为不重叠的指定长度子串。比如输入字符串长度为10、子串长度为2时，应该分割为5个不重叠子串，而非9个滑动子串。

2. 自定义排序规则未实现
   原代码使用默认的String.compareTo()方法排序，而需求要求权重相同时按* > - > +的自定义字符序排序。默认ASCII顺序为*(42) < +(43) < -(45)，与需求完全相反。

修正后的代码 #

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

class Main {
    public static void main(String[] args) throws Exception {
        StringBuilder inputData = new StringBuilder();
        String thisLine = null;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while ((thisLine = br.readLine()) != null) {
            inputData.append(thisLine + "\n");
        }
        System.out.println(codeHere(inputData));
    }

    public static String codeHere(StringBuilder inputData) {
        String[] lines = inputData.toString().split("\n");
        String inputString = lines[0].trim();
        int subStringLength = Integer.parseInt(lines[1].trim());

        return hashString(inputString, subStringLength);
    }

    public static String hashString(String inputString, int subStringLength) {
        Map<String, Integer> substringCount = new HashMap<>();
        // 修正1：按子串长度步长分割，不重叠截取
        for (int i = 0; i < inputString.length(); i += subStringLength) {
            String substring = inputString.substring(i, i + subStringLength);
            substringCount.put(substring, substringCount.getOrDefault(substring, 0) + 1);
        }

        List<String> uniqueSubstrings = new ArrayList<>(substringCount.keySet());
        uniqueSubstrings.sort((a, b) -> {
            int weightComparison = substringCount.get(b) - substringCount.get(a);
            if (weightComparison == 0) {
                // 修正2：实现自定义字符序比较
                return compareCustomOrder(a, b);
            }
            return weightComparison;
        });

        StringBuilder hash = new StringBuilder();
        for (String substring : uniqueSubstrings) {
            hash.append(substring);
        }

        return hash.toString();
    }

    // 自定义字符序比较方法：* > - > +
    private static int compareCustomOrder(String a, String b) {
        for (int i = 0; i < a.length(); i++) {
            char c1 = a.charAt(i);
            char c2 = b.charAt(i);
            if (c1 == c2) continue;
            // 优先级高的子串排前面，故c1优先级更高时返回-1（sort方法返回负则a在前）
            if (c1 == '*') return -1;
            if (c2 == '*') return 1;
            if (c1 == '-') return -1;
            if (c2 == '-') return 1;
            return Character.compare(c1, c2);
        }
        return 0;
    }
}

验证示例输入 #

输入：

-+*++-*++-
2

分割后的子串为：-+, *+, +-, *+, +-，统计结果：*+出现2次，-+和+-各出现1次。排序时，*+权重最高排第一，权重相同的-+和+-按自定义序，- > +，所以-+排第二，+-排第三，拼接后得到*++--+，与预期一致。

内容的提问来源于stack exchange，提问作者Shabbir Katlariwala