四川盐亭网站制作公司

左神算法与数据结构——基础提升KMP算法-创新互联

KMP算法

解决的问题

成都网站建设哪家好，找创新互联建站！专注于网页设计、成都网站建设、微信开发、小程序设计、集团成都定制网站等服务项目。核心团队均拥有互联网行业多年经验，服务众多知名企业客户；涵盖的客户类型包括：宴会酒店设计等众多领域，积累了大量丰富的经验，同时也获得了客户的一致赞扬！

在这里插入图片描述

  • 对于短的str2每个k位置下记录之前前缀与后缀相等的大值

在这里插入图片描述

策略

当str1中i位置与str2中0位置开始比较均相等，直至X、Y位置出现第一次不等。按照图示箭头继续比较。

在这里插入图片描述

  • 由于i1和i1-i2不减，while内语句复杂度为O(2N)

在这里插入图片描述

代码
vectorgetNexts(string str) {vectornexts(str.length());
    if (str.length() == 1) {nexts[0] = -1;
        return nexts;
    }
    nexts[0] = -1;
    nexts[1] = 0;
    int cn = 0;
    int i = 2;
    while (i< str.length()) {if (str[i - 1] == str[cn]) {nexts[i++] = ++cn;
        }
        else if (cn >0) {cn = nexts[cn];
        }
        else {nexts[i++] = 0;
        }
    }
    return nexts;
}

int KMP(string str1, string str2) {if (str1.length()< 1 || str2.length()< 1 || str1.length()< str2.length()) {return -1;
    }
    int i1 = 0;
    int i2 = 0;
    vectornexts = getNexts(str2);
    while (i1< str1.length() && i2< str2.length()) {if (str1[i1] == str2[i2]) {i1++;
            i2++;
        }
        else if (nexts[i2] == -1) {i1++;
        }
        else {i2 = nexts[i2];
        }
    }
    return i2 == str2.length() ? i1 - i2 : -1;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


分享文章：左神算法与数据结构——基础提升KMP算法-创新互联
标题链接：http://scyanting.com/article/eggeg.html

其他资讯