如何优化指定匹配规则下Java字符串比对程序的运行性能

实现玩家猜测字符串与隐藏字符串的匹配度校验逻辑，规则形式化定义如下：
设隐藏字符串为S，玩家输入的猜测字符串为Q，二者长度均为N，需要对Q中每个位置i（1 ≤ i ≤ N）计算对应匹配类型：

• 若Q[i] == S[i]，则位置i的匹配类型为correct
• 若Q[i] != S[i]，但存在位置j（1 ≤ j ≤ N）满足Q[i] == S[j]，则位置i的匹配类型为present，该类匹配需要满足以下约束：
  • S中的每个字符最多只能被一次correct或present类型的匹配占用
  • 匹配优先级始终向correct类型倾斜
  • 所有present类型的匹配场景中，优先匹配Q字符串中最靠左的待匹配位置
• 其余不满足上述条件的位置，匹配类型为absent

• 第一行输入字符串S（1 ≤ |S| ≤ 10^6），即隐藏词
• 第二行输入字符串Q（长度与S完全相等），即玩家的猜测串，题目保证两个字符串仅包含大写拉丁字母

输入：

COVER
CLEAR

输出：

correct
absent
present
absent
correct

当前编写的Java实现运行速度极慢，咨询优化提速方案，现有实现代码如下：

import java.util.*;

public class Task1 {
    private final static String cor = "correct";
    private final static String abs = "absent";
    private final static String pre = "present";
    static String[] stringArr;
    static java.util.Map<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine();
        String b = sc.nextLine();

        stringArr = new String[a.length()];
        int length1 = a.length();

        char[] arr1 = a.toCharArray();
        char[] arr2 = b.toCharArray();

        for (int i = 0; i < length1; i++) {
            if (arr2[i] == arr1[i]) {
                stringArr[i] = cor;
                map.put(i, i);
            }
        }

        for (int i = 0; i < length1; i++) {
            if (arr2[i] != arr1[i]) {
                while (stringArr[i] == null) {
                    boolean finded = false;
                    for (int j = 0; j < arr1.length; j++) {
                        if (arr2[i] == arr1[j] && !map.containsKey(j)) {
                            stringArr[i] = pre;
                            finded = true;
                            map.put(j, j);
                            break;
                        }
                    }
                    if (!finded) stringArr[i] = abs;
                }
            }
        }

        for (String s : stringArr) {
            System.out.println(s);
        }
    }
}

现有代码慢的核心原因 #

现有实现的时间复杂度是O(N²)，当字符串长度达到10^{6级别时，总运算量会达到10}12量级，必然会超时。除此之外还有几个额外的性能损耗点：

• 使用HashMap存储已占用的位置，装箱拆箱、哈希计算的开销远高于数组操作
• 处理present匹配时，每个待匹配位置都要从头遍历整个S串找可用字符，存在大量重复遍历
• 冗余的while循环判断，逻辑上完全可以去掉
• 大输入场景下Scanner和逐次println的IO开销极高

优化思路 #

因为字符只有26个大写拉丁字母，我们可以用长度为26的计数数组统计S中未被correct匹配占用的字符剩余数量，把时间复杂度降到O(N)，完全可以支撑10^6长度的输入：

1. 第一遍遍历先标记所有correct的位置，同时统计S中每个字符扣除掉correct占用后的剩余可用数量
2. 第二遍从左到右遍历Q中未标记correct的位置，如果当前字符的剩余可用计数大于0，就标记为present，同时把对应字符的剩余计数减1；如果计数为0，直接标记为absent，天然满足Q串左优先匹配的规则
3. 输入输出使用更高效的缓冲IO类，输出时提前拼接好所有结果再一次性写出，减少IO次数

优化后参考代码 #

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.nio.charset.StandardCharsets;

public class Task1 {
    private static final String COR = "correct";
    private static final String ABS = "absent";
    private static final String PRE = "present";

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in, StandardCharsets.UTF_8));
        String s = br.readLine();
        String q = br.readLine();
        int n = s.length();
        byte[] res = new byte[n]; // 用byte数组标记结果：0=absent,1=present,2=correct，比String数组更省空间、访问更快
        int[] charCnt = new int[26]; // 统计S中每个字符扣除correct匹配后的剩余可用数量

        char[] sArr = s.toCharArray();
        char[] qArr = q.toCharArray();

        // 第一遍遍历：标记所有correct位置，统计剩余可用字符数
        for (int i = 0; i < n; i++) {
            char sc = sArr[i];
            if (qArr[i] == sc) {
                res[i] = 2;
            } else {
                charCnt[sc - 'A']++;
            }
        }

        // 第二遍遍历：从左到右处理present/absent，满足左优先匹配规则
        for (int i = 0; i < n; i++) {
            if (res[i] == 2) continue;
            int charIdx = qArr[i] - 'A';
            if (charCnt[charIdx] > 0) {
                res[i] = 1;
                charCnt[charIdx]--;
            }
        }

        // 预分配空间拼接结果，一次性输出减少IO开销
        StringBuilder sb = new StringBuilder(n * 8);
        for (byte b : res) {
            switch (b) {
                case 2:
                    sb.append(COR);
                    break;
                case 1:
                    sb.append(PRE);
                    break;
                default:
                    sb.append(ABS);
            }
            sb.append('\n');
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out, StandardCharsets.UTF_8));
        bw.write(sb.toString());
        bw.flush();
    }
}

优化后代码在10^6长度输入下的运行时间可以从原来的小时级降到几十毫秒级别，完全满足性能要求。

内容的提问来源于stack exchange，提问作者Lex Bekker