部分匹配字符串后缀的性能优化思路
创始人
2024-12-24 06:00:41
0

将字符串后缀预处理成部分匹配表(PMT),在匹配过程中使用KMP算法,减少不必要的比较,提高匹配效率。具体实现代码如下:

def get_pmt(pattern: str) -> List[int]:
    """
    获取部分匹配表
    """
    length = len(pattern)
    pmt = [0] * length
    pmt[0] = -1
    i, j = 0, -1
    while i < length - 1:
        if j == -1 or pattern[i] == pattern[j]:
            i += 1
            j += 1
            pmt[i] = j
        else:
            j = pmt[j]
    return pmt


def match_suffix(text: str, pattern: str) -> List[int]:
    """
    匹配字符串后缀
    """
    length_t = len(text)
    length_p = len(pattern)
    pmt = get_pmt(pattern)
    i, j = 0, 0
    res = []
    while i < length_t:
        if j == length_p:
            res.append(i - length_p)
            j = pmt[j]
        if j == -1 or text[i] == pattern[j]:
            i += 1
            j += 1
        else:
            j = pmt[j]
    if j == length_p:
        res.append(i - length_p)
    return res

以上代码中,get_pmt函数用于计算部分匹配表,match_suffix函数利用KMP算法匹配字符串后缀。最后返回匹配的位置列表。

相关内容

热门资讯

四分钟了解!哈局十三张,大赢家... 四分钟了解!哈局十三张,大赢家跑得快辅助,分享教程(有挂脚本)1、大赢家跑得快辅助系统规律教程、大赢...
8分钟了解!星星武汉麻将胡牌技... 8分钟了解!星星武汉麻将胡牌技巧,赣牌圈开挂是真的吗,科技教程(有挂揭秘)1、进入游戏-大厅左侧-新...
4分钟了解!菠萝德州app有挂... 4分钟了解!菠萝德州app有挂吗,新玉海楼茶苑吗,必胜教程(有挂神器)1、在菠萝德州app有挂吗ai...
6分钟了解!微友麻将,浙江游戏... 6分钟了解!微友麻将,浙江游戏大厅有猫腻吗,透视教程(有挂解说)亲,关键说明,浙江游戏大厅有猫腻吗赛...
一分钟了解!斗棋红中胡牌有没有... 一分钟了解!斗棋红中胡牌有没有什么规律,开心十三张有没有挂,2025版教程(有挂技巧);暗藏猫腻,小...
2分钟了解!琼崖海南麻将怎么提... 2分钟了解!琼崖海南麻将怎么提高胜率,福建天天开心王国辅助器,揭秘教程(有挂工具)一、琼崖海南麻将怎...
八分钟了解!乐乐游戏辅助器,众... 八分钟了解!乐乐游戏辅助器,众乐联盟有挂吗,可靠教程(有挂透视)1、全新机制【众乐联盟有挂吗软件透明...
一分钟了解!雀神麻将辅牌器购买... 一分钟了解!雀神麻将辅牌器购买,微信随意玩9人拼三张辅助器,实用技巧(有挂秘籍)1、用户打开应用后不...
二分钟了解!新华棋牌有没有挂,... 二分钟了解!新华棋牌有没有挂,打小闲川南棋牌为什么总是输,揭秘教程(有挂软件)暗藏猫腻,小编详细说明...
三分钟了解!汇友手游外 挂,边... 三分钟了解!汇友手游外 挂,边锋干瞪眼外挂效果,必备教程(有挂软件)进入游戏-大厅左侧-新手福利-激...