首页 > 编程语言 >kmp算法模板

kmp算法模板

时间:2024-08-07 13:27:38浏览次数:15  
标签:string int pattern 算法 kmp pi 模板 size

模板

    // pi代表前缀函数
	// pi[i]: s[0~i]的最长匹配真前后缀长度
	vecotr<int> pi(str.size()); 


	// 求前缀函数
	for(int i=1; i<str.size(); i++){
		int len=pi[i-1]; //前一个值的pi len是我们想要找到的一个长度值
		while(len!=0&&str[i]!=str[len]){ // 不匹配时,求次小的前缀函数
			len=pi[len-1];
		}
		if(str[i]==str[len]){
			p[i]=len+1;
		}
	}

简单应用

#的作用是避免找到的字符串由模板串和待查找串两部分构成

int strStr(string s, string pattern) {
        int n=s.size();
        int m=pattern.size();
        // # 的作用,避免找到的匹配字符串是由pattern的部分+s的一部分共同构成的
        string str=pattern+"#"+s; 
        vector<int> pi(str.size()); // 前缀数组,最长匹配真前后缀长度
        for(int i=1; i<str.size(); i++){
            int len=pi[i-1];
            while(len!=0&&str[i]!=str[len]){
                len=pi[len-1];
            }
            if(str[i]==str[len]){
                pi[i]=len+1;
                if(pi[i]==m)
                    return i-2*m;
            }
        }

        return -1;
    }

参考: B站NotOnlySuccess KMP的本质

标签:string,int,pattern,算法,kmp,pi,模板,size
From: https://www.cnblogs.com/Biang-blog/p/18346848

相关文章

  • 【数据结构与算法】删除循环队列中第k个元素的算法 C++实现(循环队列+模运算)
    数组a[MaxSize]用作一个循环队列,front指向循环队列中队头元素的前一个位置,rear指向队尾元素的位置。设计删除队列中第k个元素的算法。思路首先,判断kkk是否在有效范围内......
  • 【数据结构与算法】在循环队列中第k个元素之后插入元素的算法 C++实现(循环队列+模运算
    数组a[MaxSize]用作一个循环队列,front指向循环队列中队头元素的前一个位置,rear指向队尾元素的位置。设计在队列中第k个元素之后插入item的算法。思路首先,检查输入的位置k是否在合理的范围内,即1到queueSize(Q)(包含两端)。如果k在这个范围外,那么返回ERROR。然后,计......
  • 算法力扣刷题记录 六十八【131.分割回文串】
    前言回溯章节第六篇。切割问题。记录六十八【131.分割回文串】。一、题目阅读给你一个字符串s,请你将s分割成一些子串,使每个子串都是回文串。回文串指字符串从前读和从后读一样。返回s所有可能的分割方案。示例1:输入:s="aab"输出:[["a","a","b"],["aa","b"]]......
  • Java计算机毕业设计基于协同过滤算法的商品推荐系统(开题报告+源码+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景在信息爆炸的时代,电商平台上的商品数量呈指数级增长,用户在面对海量商品时往往感到无所适从,难以快速找到符合自身需求和喜好的商品。传统的搜索方式虽......
  • 【NOI】C++算法设计入门之穷举
    文章目录前言一、概念1.导入2.概念二、例题讲解1.简单穷举问题:1015.鸡兔同笼问题问题:1351.买公园门票问题:1016.买小猫小狗问题:1220.买糕点问题:1396.开学大采购?2.嵌套穷举问题:1022.百钱百鸡问题问题:1024.购买文具问题:1249.搬砖问题问题:1250.马克思手稿的问题......
  • 织梦DEDECMS列表页首页怎么跟其它页使用不同模板
    有些时候我们需要使列表页的首页跟第二页以及后面的页面的样式不同,修改dede:list标签又很难达到理想的效果,那么织梦猫就为大家介绍一个最简单的办法,就是为首页单独指定一个模板页,其余页面则调用另一个模板页。修改的办法如下:打开include目录下的arc.listview.class.php文件,找到D......
  • 「代码随想录算法训练营」第三十一天 | 动态规划 part4
    1049.最后一块石头的重量II题目链接:https://leetcode.cn/problems/last-stone-weight-ii/题目难度:中等文章讲解:https://programmercarl.com/1049.最后一块石头的重量II.html视频讲解:https://www.bilibili.com/video/BV14M411C7oV/题目状态:看题解过思路:本题本质上就是将......
  • 代码随想录算法训练营第62天 | 最短路径:dijkstra(堆优化版)+ Bellman_ford算法
    47.参加科学大会https://kamacoder.com/problempage.php?pid=1047dijkstra(堆优化版)精讲https://www.programmercarl.com/kamacoder/0047.参会dijkstra堆.html#思路94.城市间货物运输Ihttps://kamacoder.com/problempage.php?pid=1152Bellman_ford算法精讲https://www.pr......
  • 排序算法
    排序算法BUBSort冒泡排序伪代码do-swapped=false-fromi=1to最后一个没有排序过元素的索引-1-ifleft>right--swap(left,right)--swapped=truewhileswapped代码实现voidBubSort(){inttem=0;boolswapped;do{t......
  • 代码随想录算法训练营第61天 | 图论part08:拓扑排序+迪杰斯特拉朴素法
    117.软件构建https://kamacoder.com/problempage.php?pid=1191拓扑排序精讲https://www.programmercarl.com/kamacoder/0117.软件构建.html#拓扑排序的背景47.参加科学大会https://kamacoder.com/problempage.php?pid=1047dijkstra(朴素版)精讲https://www.programmercarl.c......