基于KMP算法JavaScript的实现方法分析

算法的核心是部分匹配表和回退算法，部分匹配表的实现如下：


代码如下:

function kmpGetStrPartMatchValue(str) {
    var prefix = [];
    var suffix = [];
    var partMatch = [];
    for(var i=0,j=str.length;i<j;i++){
        var newStr = str.substring(0,i+1);
        if(newStr.length == 1){
            partMatch[i] = 0;
        } else {
            for(var k=0;k<i;k++){
                prefix[k] = newStr.slice(0,k+1);
                suffix[k] = newStr.slice(-k-1);
                if(prefix[k] == suffix[k]){
                    partMatch[i] = prefix[k].length;
                }
            }
            if(!partMatch[i]){
                partMatch[i] = 0;
            }
        }
    }
    prefix.length = 0;
    suffix.length = 0;
    return partMatch;
}

//demo
var t="ABCDABD";
console.log(kmpGetStrPartMatchValue(t));
//output:[0,0,0,0,1,2,0]

回退算法实现如下：


代码如下:

function KMP(sourceStr,targetStr){
    var partMatchValue = kmpGetStrPartMatchValue(targetStr);
    var result = false;
    for(var i=0,j=sourceStr.length;i<j;i++){
        for(var m=0,n=targetStr.length;m<n;m++){
            if(str.charAt(m) == sourceStr.charAt(i)){
                if(m == targetStr.length-1){
                    result = true;
                    break;
                } else {
                    i++;
                }
            } else {
                if(m>0 && partMatchValue[m-1] > 0){
                    m = partMatchValue[m-1]-1;
                } else {
                    break;
                }
            }
        }
        if(result){
            break;
        }
    }
    return result;
}
var s = "BBC ABCDAB ABCDABCDABDE";
var t = "ABCDABD";
console.log(KMP(s,t));
//output: true

赞 (0)

相关推荐

  • C#实现排列组合算法完整实例

    排列组合是常见的数学问题,本文就以完整实例形式讲述了C#实现排列组合算法的方法.分享给大家供大家参考之用.具体方法如下: 首先,数学中排列组合,可表示为:排列P(N,R) 其实排列实现了,组合也就实现了,组合C(N,R)就是P(N,R)/P(R,R) ,实现这一功能比较简单的是递归算法,但考虑到递归的性能,下面采用了2种非递归的方法,具体代码如下 using System; using System.Collections.Generic; namespace Test { class Prog

  • c语言中使用BF-KMP算法实例

    直接上代码 复制代码 代码如下: #define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h> #define MAX_SIZE 255    //定义字符串的最大长度 typedef unsigned char SString[MAX_SIZE];//数组第一个保存长度//BFint BFMatch(char *s,char *p){    int i,j;  

  • C语言实现字符串匹配KMP算法

    C语言实现字符串匹配KMP算法

    字符串匹配是计算机的基本任务之一. 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"? 下面的的KMP算法的解释步骤 1. 首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较.因为B与A不匹配,所以搜索词后移一位. 2. 因为B与A不匹配,搜索词再往后移. 3. 就这样,直到字符

  • C#常见算法面试题小结

    本文实例汇总了C#面试常见的算法题及其解答.具有不错的学习借鉴价值.分享给大家供大家参考.具体如下: 1.写出冒泡,选择,插入排序算法. //冒泡排序 public class bubblesorter { public void sort(int[] list) { int i, j, temp; bool done = false; j = 1; while ((j < list.Length) && (!done)) { done = true; for (i = 0; i &

  • KMP算法的C#实现方法

    本文实例简述了KMP算法的C#实现方法,分享给大家供大家参考.具体如下: 具体思路为:next函数求出模式串向右滑动位数,再将模式串的str的next函数值 存入数组next. 具体实现代码如下: static void GetNextVal(string str, int [] next) { int i = 0; int j = -1; next[0] = -1; while (i < str.Length - 1) { if (j == -1 || str[i] == str[j]) {

  • c#获取相同概率随机数的算法代码

    这几天在做公司年会的一个抽奖软件,开始做的的时候,认为算法是很简单的,把员工的数据放进list里,把list的标号作为需要获取的随机数,根据得到的随机数就确定是谁中奖.后来测试发现,随机数的分布是非常不均匀的.后来才知道,原来计算机获取的随机数都是伪随机数,当抽奖的速度非常快的时候,获取的随机数是非常不均匀的,所以在每次抽奖的时候要添加延时.后来重新设计算法,最终实现了. 算法原理跟二分查找的过程有点像.一枚硬币抽中正.反面的概率是一样,当抽样的次数无限增多,抽中的概率是50%. 代码如下: 复

  • c#哈希算法的实现方法及思路

    c#哈希算法的实现方法及思路

    有想过hash["A1"] = DateTime.Now;这句是怎么实现的吗?我们来重温下学校时代就学过的哈希算法吧. 我们要写个class,实现如下主程序调用: 复制代码 代码如下: static void Main(string[] args)        {            MyHash hash = new MyHash();            hash["A1"] = DateTime.Now;            hash["A2

  • C# DES加密算法中向量的作用详细解析

    DES一共就有4个参数参与运作:明文.密文.密钥.向量.为了初学者容易理解,可以把4个参数的关系写成:密文=明文+密钥+向量:明文=密文-密钥-向量.为什么要向量这个参数呢?因为如果有一篇文章,有几个词重复,那么这个词加上密钥形成的密文,仍然会重复,这给破解者有机可乘,破解者可以根据重复的内容,猜出是什么词,然而一旦猜对这个词,那么,他就能算出密钥,整篇文章就被破解了!加上向量这个参数以后,每块文字段都会依次加上一段值,这样,即使相同的文字,加密出来的密文,也是不一样的,算法的安全性大大提高!

  • c#冒泡排序算法示例

    复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace 冒泡排序{    class Program    {        static void swap( ref int  atemp, ref int  btemp)//注意ref的使用        {            int temp = atemp;            at

  • C#的3DES加密解密算法实例代码

    C#类如下: 复制代码 代码如下: using System;using System.Collections.Generic;using System.Text;using System.Security.Cryptography;using System.IO; namespace ConsoleApplication1{    /// <summary>    /// 加解密类    /// </summary>    public class EncryptHelper  

  • C#实现协同过滤算法的实例代码

    复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace SlopeOne{    public class Rating    {        public float Value { get; set; }        public int Freq { get; set; }        public float AverageValue

随机推荐