Javascript如何实现获取所有不重叠子串匹配索引的功能

完整实现代码 #

function splitVars(eq, vars) {
    // 按子串长度降序排序，长匹配优先处理，避免被短匹配抢占位置
    const sortedVars = [...vars].sort((a, b) => b.length - a.length);
    const strLen = eq.length;
    // 标记数组：记录字符串每个位置是否已经被匹配占用
    const occupied = new Array(strLen).fill(false);
    const validLocs = [];

    for (const variable of sortedVars) {
        const varLength = variable.length;
        // 拿到当前子串的所有原始匹配索引
        const allIndexes = locations(variable, eq);
        // 过滤掉和已占用位置重叠的无效索引
        const validIndexes = allIndexes.filter(start => {
            for (let i = start; i < start + varLength; i++) {
                if (occupied[i]) return false;
            }
            return true;
        });
        // 将合法索引对应的字符位置标记为已占用
        validIndexes.forEach(start => {
            for (let i = start; i < start + varLength; i++) {
                occupied[i] = true;
            }
        });
        validLocs.push({
            variable,
            varLength,
            indexes: validIndexes
        });
    }

    // 按合法匹配拆分字符串
    const allMatches = [];
    validLocs.forEach(({variable, varLength, indexes}) => {
        indexes.forEach(start => {
            allMatches.push({start, end: start + varLength, text: variable});
        })
    });
    // 所有匹配按起始位置升序排序
    allMatches.sort((a, b) => a.start - b.start);

    const result = [];
    let lastPos = 0;
    allMatches.forEach(match => {
        // 拼接匹配区间前的普通字符
        if (match.start > lastPos) {
            result.push(eq.slice(lastPos, match.start));
        }
        // 拼接匹配到的子串
        result.push(match.text);
        lastPos = match.end;
    });
    // 拼接末尾剩余的普通字符
    if (lastPos < strLen) {
        result.push(eq.slice(lastPos));
    }

    return {
        // 去重后的匹配索引数组
        filteredLocs: validLocs,
        // 最终拆分结果
        splitResult: result
    };
}

function locations(substring, string){
    const a = [];
    let i = -1;
    while((i = string.indexOf(substring, i + 1)) >= 0) a.push(i);
    return a;
}        

// 测试用例1：你给出的matatatatt示例
console.log(splitVars('matatatatt', ['at', 't']).splitResult); 
// 输出： ['m', 'at', 'at', 'at', 'at', 't']

// 测试用例2：你原代码的测试输入
console.log(splitVars('wmtmtmtt', ['mt', 't']).splitResult);

核心逻辑说明 #

• 长匹配优先处理：先对输入的子串数组按长度从大到小排序，保证长匹配先占用对应的字符位置，不会被短匹配覆盖
• 重叠索引过滤：通过标记数组记录已被占用的字符位置，短匹配的索引如果对应区间存在已占用的位置，直接过滤丢弃
• 拆分拼接：把所有合法匹配按位置排序后，依次拼接未匹配的普通字符和匹配到的子串，得到最终拆分结果

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