洛谷P5410 【模板】扩展 KMP【捂着良心说真的很detailed,很久没这么认真了www】

本文主要是介绍洛谷P5410 【模板】扩展 KMP【捂着良心说真的很detailed,很久没这么认真了www】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

扩展KMP

  • 定义:给定字符串 s 和 t ,求 s 的后缀 最大相同前缀的长度。以extend[ i ]表示 s [ i, s_len ) 和 t [ 0, t_len ) 的最大相同前缀的长度。此外定义Next[ i ]表示 t [ i , t_len ) 和 t 的最大相同前缀的长度。

举个栗子

知道了Next[] 和 extend[ ]的定义,很好模拟出来上面的答案。


那么如何求得extend[ ]呢?

我们假设当前遍历到了 s 串的 i 位置,也就是extend[ k ] (k < i) 都已知了。那么定义两个变量 front 和 p,p表示 s 串从front开始和 t 串匹配的最右边界。即s[front, p) = t[0, p-front)

再者,我们假设Next[]是已知的。

此时我们知道Next[ i - front ],也就是上图红方框的长度。由Next[]的定义我们可以知道上图中t串上的两个红方框是相等长度。

所以当i + Next[i - front] < p时,extend[ i ] = Next[i - front]

当i + Next[i - front] > p时,因为s[p] != t[p - front],而t[p - front] == t[p - i],所以s[p] != t[p - i],所以已经没有继续往下匹配的需要了。

所以当i + Next[i - front] > p时,extend[ i ] = p - i

那么话说回来了,如果i + Next[i - front] == p呢?因为s[p] != t[p - front],而t[p - front] != t[p - i],但是可能s[p] == t[p - i],这样我们只需要从t[p - i]开始往后继续匹配。


那么Next[]又怎么求呢?

由定义我们可以知道 Next[] 就是 t[i, t_len) 和 t 的匹配,和上面是一样的。


那么接下来就是代码啦~

void GetNext(char *t, int len)
{int front = 0, p = 0;Next[0] = len;for(int i = 1; i < len; i ++ ){if(i >= p || i + Next[i - front] >= p){if(i >= p) p = i;while(p < len && t[p] == t[p - i]) ++ p;Next[i] = p - i;front = i;}elseNext[i] = Next[i - front];}
}
void GetExtend(char *s, int s_len, char *t, int t_len)
{GetNext(t, t_len);int front = 0, p = 0;for(int i = 0; i < s_len; i ++ ){if(i >= p || i + Next[i - front] >= p){if(i >= p) p = i;while(p < s_len && p - i < t_len && s[p] == t[p - i]) ++ p;extend[i] = p - i;front = i;}elseextend[i] = Next[i - front];}
}

怎么说呢,这个还是理解了很久的,不知道别个在写什么。写的看不懂,就是使劲想使劲想吧,突然就开窍了。嘻嘻嘻~附上参考博客~ 开始的时候还觉得人家写错了,差点就评论了,……还好矜持了一下!嗐!

即使我再怎么讨厌打错字,还是避免不了会打出来错字,尤其是写文章的时候。所以鸭,更不用说博客写算法详解了,如果有错误请大家不吝赐教喔~话说回来这一年我还真的写了很多很多。虽然大多都是日记,虽然也有手写日记的,但是很多都是写在网上(当然是隐私的,涉及隐私www)。但是真的写了得有好多好多字了(陈美嘉专用“好多好多”~盗用一下嘻嘻)。大多都是有感而发,开心的,难过的,都有写。也有很多是给自己加油鼓劲的话~毕竟不是一个说能静下心来学习就可以的人~不知道如果我写的文章发出来会不会有浏览量哈哈哈。我jio的可以考虑玩哈公众号,等退役了哈哈哈哈哈~【讲真不觉得自己是个现役队员www,好菜喔】


 洛谷P5410 【模板】扩展 KMP

  • 输出扩展KMP的Next数组和extend数组。

AC CODE

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxN = 100000 + 7;
int Next[maxN], extend[maxN];
void GetNext(char *t, int len)
{int front = 0, p = 0;Next[0] = len;for(int i = 1; i < len; i ++ ){if(i >= p || i + Next[i - front] >= p){if(i >= p) p = i;while(p < len && t[p] == t[p - i]) ++ p;Next[i] = p - i;front = i;}elseNext[i] = Next[i - front];}
}
void GetExtend(char *s, int s_len, char *t, int t_len)
{GetNext(t, t_len);int front = 0, p = 0;for(int i = 0; i < s_len; i ++ ){if(i >= p || i + Next[i - front] >= p){if(i >= p) p = i;while(p < s_len && p - i < t_len && s[p] == t[p - i]) ++ p;extend[i] = p - i;front = i;}elseextend[i] = Next[i - front];}
}
char s[maxN], t[maxN];
int main()
{while(~scanf("%s%s", s, t)){int s_len = strlen(s);int t_len = strlen(t);GetExtend(s, s_len, t, t_len);for(int i = 0; i < t_len; i ++ )printf("%d%c", Next[i], " \n"[i == t_len - 1]);for(int i = 0; i < s_len; i ++ )printf("%d%c", extend[i], " \n"[i == s_len - 1]);}return 0;
}

 

这篇关于洛谷P5410 【模板】扩展 KMP【捂着良心说真的很detailed,很久没这么认真了www】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/225232

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

poj 2104 and hdu 2665 划分树模板入门题

题意: 给一个数组n(1e5)个数,给一个范围(fr, to, k),求这个范围中第k大的数。 解析: 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码: poj 2104: #include <iostream>#include <cstdio>#include <cstdlib>#include <al

最大流、 最小费用最大流终极版模板

最大流  const int inf = 1000000000 ;const int maxn = 20000 , maxm = 500000 ;struct Edge{int v , f ,next ;Edge(){}Edge(int _v , int _f , int _next):v(_v) ,f(_f),next(_next){}};int sourse , mee

Spring框架5 - 容器的扩展功能 (ApplicationContext)

private static ApplicationContext applicationContext;static {applicationContext = new ClassPathXmlApplicationContext("bean.xml");} BeanFactory的功能扩展类ApplicationContext进行深度的分析。ApplicationConext与 BeanF