美文网首页
kmp中部分匹配表的计算

kmp中部分匹配表的计算

作者: 舒小贱 | 来源:发表于2020-04-08 21:28 被阅读0次
/*
思路就是:遍历pattern字符串,每新加一个letter:
对于prefix列表,都是原来元素不动,新加上一个pattern[:idx]元素
suffix列表,对其中的每个元素拼接上letter,然后新加一个值为letter的元素

然后比较prefix和suffix列表相同的元素(prefix和suffix的个数和长度都是一一对应的,所以这里只需要遍历一次prefix或suffix,而不是对prefix和suffix做两层遍历),计算相同元素中的最大长度。
**/
func main() {
    
    pattern := "AAACAAAAAC" //lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
    table := getPatternTable(pattern)
    res, _ := json.Marshal(table)
    fmt.Println(string(res))
}




func getPatternTable(p string) []int {
    table := []int{0}

    var prefix []string
    var suffix []string
    for idx := 1; idx < len(p); idx++ {

        dd := 0
        prefix = append(prefix, p[:idx])
        for i := 0; i < len(suffix); i++ {
            suffix[i] = suffix[i] + string(p[idx])
        }
        suffix = append(suffix, string(p[idx]))
        for i := 0; i < len(prefix); i++ {
            if prefix[i] == suffix[len(prefix)-1-i] {
                if len(prefix[i]) > dd {
                    dd = len(prefix[i]) //共同的前后缀的最长长度,而不是个数
                }
            }
        }
        table = append(table, dd)
    }
    return table
}

对于参考中计算lps列表的算法,还是没理解过来。

相关文章

  • 字符串查找匹配--kmp算法

    部分匹配表 KMP的关键是部分匹配表。理解KMP的主要障碍是没有完全掌握部分匹配表中的值到底意味着什么。试着用最简...

  • kmp中部分匹配表的计算

    对于参考中计算lps列表的算法,还是没理解过来。

  • 匹配算法

    部分匹配表中i=pnext[i]相当于一个小的KMP

  • 理解KMP算法

    简单理解KMP 本文读者可以获得两方面的知识 直观理解如何生成部分匹配表(下文简称匹配表),这是KMP算法的核心思...

  • (302)查找-KMP字符串匹配

    概述 kmp算法我觉得有两个关键点:1.计算模式字符串的部分匹配表(这时候,自己跟自己比较)2.匹配主串时候,主串...

  • KMP算法(javascript实现)

    KMP算法是很经典的字符串匹配算法,主要通过部分匹配表来提高匹配效率。具体的算法步骤可以看文章这里[http://...

  • KMP算法的理解及其C语言的实现

    KMP的概念网上有很多介绍,核心是理解PMT(Partial Match Table,部分匹配表),而next数组...

  • KMP(一) 模式匹配算法推导 --《部分匹配表》

    概述:本文主要在理论层面上分析KMP的基本实现原理以及《部分匹配表》推导过程;不涉及代码实现;如果您对KMP的实现...

  • 一些有关算法的

    字符串模式匹配算法 字符串的KMP算法详解部分匹配表(即)向右移一位就可以得到next数组。字符串模式匹配算法 R...

  • KMP

    KMP有什么用 KMP主要应用在字符串匹配上。 KMP的主要思想是「当出现字符串不匹配时,可以知道一部分之前已经匹...

网友评论

      本文标题:kmp中部分匹配表的计算

      本文链接:https://www.haomeiwen.com/subject/tvixmhtx.html