链表可以用指针加结构体的实现方式 ?? 动态链表
在面试题中用得比较多，在笔试题中不常见
栈、队列都可以直接使用 stl 中的容器
但是如何用数组模拟链表、栈与队列？静态链表
为什么要用数组模拟呢？
效率问题：如果用指针加结构体的方式来实现链表的话，每次创建一个新的节点的时候，就要调用 new Node()，每次 new 一个新的节点。但是这个操作是非常慢的，笔试中一般不采用这种动态链表的方式(笔试中链表的大小一般为 10 w 级别 ~ 100 w 级别，单单把这 10 w 个节点 new 出来都会导致超时)
用数组模拟单链表
单链表最初的状态：有一个头节点，头节点最一开始是指向空节点，每次往里面插入一个新的元素
单链表在笔试题最大的用途是用来写邻接表( n 个链表)：用于存储树 (最小生成树问题) 和图 (最短路问题)
单链表的长相：每一个点都会存储两个值：一个 val(当前点表示的值是多少)、一个 next 指针(下一个点的位置在什么地方)，链式的形状
用数组来模拟需要定义的东西如下：
①需要定义每个节点的 val
②每个点的 next 指针
用 e[ N ] 来表示某个点的值是多少，用 ne[ N ] 来表示某个点的 next 指针是多少，e[ N ] 和 ne[ N ] 都是整型数组
e[ N ] 和 ne[ N ] 是怎么关联起来的呢？
e[ N ] 和 ne[ N ] 是用下标关联起来的，下图就是链表在数组中的表现方式：每个节点有两个值，e[ N ] 和 ne[ N ]
把每一个节点都存储到数组中，这些节点都有一个编号，假设第一个节点编号是 0，第二个节点编号是 1. . .空节点的编号用 -1 来表示
单链表的性质：可以用 O(1) 的时间直接找到下一个点的位置，但是找不到上一个点的位置
单链表是只往后看，不往前看的
如果想找到当前点的前面那个点(找 1 号点前面那个点)，只能从头开始遍历
如果想遍历整个链表的话，可以沿着这条边，把整个链表遍历一遍
链表最一开始为空，需要给它不断分配新的点，不断往里面插入新的点，idx 相当于是一个指针，一开始总共分配了 n 个点的位置，idx 是一个指针，从第 1 个点开始，当我们需要分配一个新的点的时候，就把当前 idx 这个指针指向的节点分配给它，然后把 idx 指针往后移动一位
单链表可以在任意位置插入，但是如果想在 O（1）的时间复杂度之内插入的话，就只能在某一个点后面一个点插入
题目保证所有操作都是合法的，不用担心删除 一 个已经删除的节点 或者说，在第 k 个插入点后面插入一个数的话，第 k 个插入点一定是存在的
示例：
最一开始 head 指向空
①H 9 在头节点的位置插入 9
②在第 一 个插入点 (下标是 0 的点) 后面插入 一 个新的点
③删除第一个插入的点 (删除编号是 0 的点)
④当 k 等于 0 时，表示删除头节点，整个链表都被删除了
⑤H 6 在头节点的位置插入 6 (注意：这是第 3 个插入点，下标 idx 是 2)
⑥在第 3 个插入点后面插入一个新的点 6
⑦在第 4 个插入点后面插入一个新的点 5
⑧再在第 4 个插入点后面插入一个新的点 5
⑨在第 3 个插入点后面插入一个新的点 4
⑩删除第 6 个插入点 (把下标 idx 是 5 的点删除)
如何往链表中插入一个点？
有很多个可以插入的地方：
1.将一个新节点 x 插到头节点的位置
2.将一个新节点 x 插入到下标为 k 的点后面?
删除一个点，idx 不变 (删除的点当作它不存在，一般不需要考虑，不需要考虑是否会浪费内存空间、是否会出现内存泄漏的问题）
?
题目要求实现一个单链表，head 一 开始指向空，需要支持三种不同的操作，最后输出整个链表
删除第 k 个插入的数后面的数：删除下标是 k - 1 的点的后面一个点
idx 一 开始等于 0，每次插入一个新的点之后，idx ++，因此第一个插入点的下标是 0，第二个插入点的下标是 1，第三个插入点的下标是 2. . .第 k 个插入点的下标是 k - 1
在第 k 个插入的数后插入一 个数：在下标是 k - 1 的点后面插入一个新的点
第 k 个插入的数其实就是下标是 k - 1 的点
#include<iostream>
using namespace std;
const int N = 100010;
//head 表示头结点的下标-> 所有的节点都是可以用下标来索引的: 下标为0的节点为 e[0] 和 ne[0] 下标为1的节点为 e[1] 和 ne[1]
//e[i] 表示节点 i 的值是多少
//ne[i] 表示节点 i 的 next 指针是多少-> 节点 i 的下一个点的下标是什么
//idx 用来存储当前已经用到了哪个点
int head,e[N],ne[N],idx;
//初始化链表
void init()
{
//刚开始链表为空 head 指向-1
head = -1;
//表示当前可以从0号点开始用-> 每一个点都没有被分配
idx = 0;
}
//将一个新节点 x 插到头节点的位置-> 加入红色指针
void add_to_head(int x)
{
//存储 x 这个值
e[idx] = x;
//将红色指针指向 head 指向的值
ne[idx] = head;
//让 head 指向红色指针
head = idx;
//当前 idx 的位置已经被使用了 idx 移到下一个位置
idx++;
//e[idx] = x,ne[idx] = head,head = idx++;
}
//将一个新节点 x 插入到下标是 k 的点后面-> 把红色的点插到 2 号点后面
void add(int k,int x)
{
//存储 x 这个值
e[idx] = x;
//先让红色的 next 指针指向 k 这个点的下一个位置
ne[idx] = ne[k];
//让 k 这个点的下一个位置指向红色的点
ne[k] = idx;
idx++;
}
//将下标是 k 的点后面的点删掉-> 想把 1 号点后面这个点 2 号点删掉
void remove(int k)
{
//直接让 1 号点的next指针指向 2 号点的next指针 ne[1]=2,ne[ne[1]]=3
ne[k] = ne[ne[k]];
}
int main()
{
int m;
//读入 m 个操作 每个操作是一个字符
cin >> m;
//初始化链表
init();
while(m--)
{
int k,x;
char op;
//首先读入一个操作
cin >> op;
//在头节点插入一个数
if(op == 'H')
{
//读入要插入的数是什么
cin >> x;
//调用函数
add_to_head(x);
}
//删除第 k 个数
else if(op == 'D')
{
cin >> k;
//特判: 如果 k 等于 0 的话是删除头节点-> 让头节点直接指向它指向这个点的下一个点
if(!k) head = ne[head];
//一定要注意下标是k - 1-> 下标是从0开始的,0号点是第一个插入点,1号点是第二个插入点,第k个插入点的下标是k - 1
remove(k - 1);
}
//在第 k 个数后面插入一个数 x
else
{
cin >> k >> x;
add(k - 1,x);
}
}
//遍历整个链表-> 从头节点开始 如果 i 没有遍历到空节点 每次 i 往后走一步并输出当前 i 的值
for(int i = head;i != -1;i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}用数组模拟双链表
用于优化某些问题
单链表的每一个节点只有一个指向后面的指针??
双链表的每一个节点有两个指针，一个指向前，一个指向后
int l[ N ] 存储每一个点左边的点是什么，int r[ N ] 存储每一个点右边的点是什么
这里不定义头节点和尾节点，直接让下标是 0 的点是左边的点 head、下标是 1 的点是最右边的点 (最后一个点) tail
最一开始的状态：0 号点的右边等于 1 号点，1 号点的左边等于 0 号点， 0 号点和 1 号点其实是两个边界
如何插入一个点？
有两种选择，可以插到某个点的左边，也可以插在某个点的右边，假设想在第 k 个点的右边插入一个点 x，一共要改变四条边，有四个指针操作
先建立下图的两个红色指针
?
在 k 的左边插入一个新的点，相当于在 l[k] 的右边插入一个新的点 (在 k 的左边这个点的右边插入 x 与 在 k 的左边插入时一样的)
???
删除第 k 个点，只有两个指针的操作
#include<iostream>
using namespace std;
/*
struct Node
{
int e,l,r;
}nodes[N];
*/
const int N = 100010;
//表示某个点的值 每个点左边的点是谁 每个点右边的点是谁
int e[N],l[N],r[N],idx;
//初始化
void init()
{
//0 表示左端点,1 表示右端点
r[0] = 1,l[1] = 0;
//由于 0 和 1 已经被占用了-> idx从2开始
idx = 2;
}
//在下标是 k 的点的右边插入一个点 x
void add(int k,int x)
{
//先赋值
e[idx] = x;
//红色点右边的指针指应该等于k右边的指针
r[idx] = r[k];
//红色点左边的指针应该指向 k
l[idx] = k;
//把两个指针重新归位
//注意不能写反了-> 先调用l[r[k]] 再修改r[k]-> 假设先把r[k]修改了 调用l[r[k]]的时候,r[k]就是修改后的值
//k后面那个点的左边指向红色的点
l[r[k]] = idx;
//k 指针的右边指向红色点
r[k] = idx;
}
//删除第 k 个点
void remove(int k)
{
//让这个点的左边(l[k])的右边直接等于右边
r[l[k]] = r[k];
//让这个点的右边(r[k])的左边直接等于左边
l[r[k]] = l[k];
/* nodes[nodes[k].l].r = nodes[k].r; */
}邻接表
开了 n 个单链表，把每个点的所有临边全部存储下来
head[ i ] 用链表存储第 i 的点所有的临边
用数组模拟栈
什么是栈？
先进后出，后放进去的元素先拿出来
下标是从 0 开始或者从 -1 开始都可以
#include<iostream>
using namespace std;
const int N = 100010;
//定义栈 栈顶下标
int stk[N],tt;
//插入一个元素-> 在栈顶上加上一个新的元素
stk[ ++ tt ] = x;
//删除一个元素-> 让栈顶下标-- 弹出
tt--;
//判断栈是否为空
if(tt > 0) not empty
else empty
//取栈顶元素
stk[tt]用数组模拟队列
什么是队列？
先进先出，先放进去的元素先拿出来
在队尾插入元素，在队头弹出元素
#include<iostream>
using namespace std;
const int N = 100010;
//定义队列 队头 队尾
int q[N],hh,tt = -1;
//在队尾插入一个元素
q[ ++tt ] = x;
//弹出一个元素 把队头指针往后移动一位
hh ++ ;
//判断队列是否为空
if(hh <= tt) not empty
else empty
//取队头元素
q[hh]
//取队尾元素
q[tt]单调栈
给定一个序列，求一下在这个序列当中的每一个数 左 / 右边离它最近的、且比它小 / 大的数 是什么，如果不存在返回 -1
①3 不存在，返回 -1
②4 左边离它最近，且比它小的数是 3，返回 3
③2 左边所有数都比它大，返回 -1
④7 左边离它最近，且比它小的数是 2，返回 2
⑤5 左边离它最近，且比它小的数是 2，返回 2
单调栈的考虑方式和双指针类似，先想暴力做法，再挖掘一些性质，把目光集中到比较少的状态中，从而起到把一个问题的时间复杂度降低的效果
暴力做法如下：求每个数 左边离它最近且比它小的这个数 的位置
两重循环，第一重循环枚举每一个数，第二重循环从 i - 1 开始枚举(从 i 左边第一个数开始枚举，一直往左走，直到找到第一个比 i 小的数为止，这个数就是 i 左边离它最近且比它小的数)
发掘暴力做法中的性质：随着 i 往右走的过程当中，可以用一个栈来存储 i 左边所有的元素（最一开始栈为空，i 指针每往右边移动一个位置，就往栈里面加入一个新的数）
每一次找是从栈顶往后找，找到第一个比 i 小的数为止就停下来
x 轴是下标，y 轴是它们的值
由于第 2 点比第 1 个点小，而且第 2 个点在第 1 个点的右边，因此第 1 个点就可以被删掉了，同理把所有逆序的点全部删掉，最后剩下的所有点一定是一个单调上升的序列
会不会有些元素永远都不会作为答案输出呢？
如果 a3 ≥ a5，a3 永远都不会作为答案输出，由于 a5 在 a3 的右边，而且 a5 比 a3 小(或相等)，在寻找的过程中，如果 a3 能够作为目标值(a3 ＜ ai)，那么 a5 一定会更好(由于a5 ＜ a3，因此 a5 ＜ ai，并且要找离 i 最近的比 i 最小的数，所以 a3 一定不会被用到)
只要以下逆序的关系，前面的数 ax 就会被删掉
假设当前栈中元素已经单调上升，到达 i 的位置，想找到左边第 1 个比 i 小的数在什么地方，可以从栈顶 stk[ tt ] 开始找，只要栈顶大于等于 ai （ ai 需要插入到栈中，ai 是比栈顶要小的，而且 ai 在更右边，因此 ai 比当前栈顶更好) ，栈顶就永远不会被当成答案，需要删除栈顶. . .一直做删除，直到删除到一个小于 ai 的为止，此时的 stk[ tt ] 就是要找的 ai 的左边离它最近且比它小的数，最后把 ai 插入到栈中
每一个元素只会进栈一次，而且每个元素最多只会出栈一次，最多也有 2n 次操作，整个算法的时间复杂度为 O( n )
输入数据比较多，读入比较慢，需要优化：
cin 比 scanf 慢了10倍左右，cin 加 ios::sync_with_stdio(false) 会快约 200 ms，cin.tie(0)
#include<iostream>
using namespace std;
const int N = 100010;
int n;
int stk[N],tt;
int main()
{
//ios::sync_with_stdio(false);
//scanf("%d",&n);
cin >> n;
//读入 n 个数
for(int i = 0;i < n;i++)
{
int x;
//读入当前这个数
cin >> x;
//栈不为空 并且栈顶元素大于等于当前这个数-> 栈顶元素永远不会被用到
while(tt && stk[tt] >= x) tt --;
//如果此时栈不为空 说明栈顶元素就是满足条件的数直接输出
if(tt) cout << stk[tt] << endl;
//栈为空 说明 x 左边没有任何一个数比它小
else cout << -1 << ' ';
//把 x 插到栈中
stk[ ++ t] = x;
}
}单调队列
求滑动窗口中的最大值 / 最小值，一共有 n 个数，要求把长度为 3 的滑动窗口中的最大值和最小值都输出出来
每次把窗口往右滑动一位，第一遍把滑动窗口中的最小值输出出来，第二遍把滑动窗口中的最大值输出出来
在问题中抽象出模型，用单调队列来优化
?
先来想一下暴力怎么做，把没有用的元素删除，得到单调性，有单调性再求极值，可以直接拿第一个点或者最后一个点，把原来有枚举一遍的时间复杂度变成 O( 1 )?
可以用队列来维护窗口，窗口一开始长度是 3，保证队列中时时刻刻存储的都是当前窗口中的所有元素，每次移动分两步来操作：
①把新元素插到队尾
②把滑出去的元素从队头弹出去
每次求极值的时候，暴力做法：直接遍历队列中的所有的元素，时间复杂度为 O( k )（假设窗口中有 k 个元素）
整个算法时间复杂度为 O( nk )
优化：看队列中是否有些元素是没有用的，把没有用的元素删掉，看是否能够得到单调性
当 - 3 进到队列后，第 1 个 3 就一定没有用了(每次求的是队列中的最小值)，- 3 是小于第 1 个 3 的，而且第 1个 3 在 - 3 的左边，第 1 个 3 会被先弹出去， - 1 也是一样，- 3 会在 -1 后面被弹出去， - 3 ≤ - 1，- 1 也不会被当作最小值输出
只要前面有一个数比后面的数大，前面的点就一定没有用：由于后面的点会被后弹出，而且比前面的数小
只要以下逆序的关系，就把大的点删掉，把所有的逆序点删掉后，最后会变成严格单调上升的队列
最终要求单调上升队列中的最小值就是队头（端点） q[ hh ]
找值：二分
队头元素什么时候出队？
已知当前枚举的右端点 i 和 区间的长度 k，队列里存储的不是值，存储的是下标，可以直接判断队头的下标是否超出了从 i - k + 1 到 i 这个范围，如果超出的话就把队头删掉
将队列置空，队尾进元素，队首出元素。当每个节点入队列时，判断队列尾部元素和该元素的大小，如果当前元素小于队列尾部元素，则将队列尾部元素出栈，再逐一比较，直到遇到小于当前元素的队列尾部元素，或者将队列置空（ while(hh <= tt && a[ q[tt] ] >= a[i] ) tt–；）
最后将该元素输入该队列（ q[ ++ tt ] = i；// 存放的下标 ）
此时创建的就是一个单调递增队列。注意窗口大小为 k，因此要加一个判断语句，来判断窗口内的元素是否要出队了（ if(hh <= tt && i - k + 1 > q[hh]) hh++；）
一定需要注意的是 q[tt++] = i 入队的过程需要放到判断之前，即如果因为当前入队元素很小，将队列给清空了，那么当前应该打印这个元素，所以应该放在判断之前
要注意头 k-1 个插入的元素不输出最小值或者最大值，因为窗口还没满 if(i >= k-1)
我们用 q 来表示单调队列，p 来表示其所对应的在原列表里的序号
由于此时队中没有一个元素，我们直接令 1 进队。此时，q={1},p={1}。
现在 3 面临着抉择。下面基于这样一个思想：假如把 3 放进去，如果后面 2 个数都比它大，那么 3 在其有生之年就有可能成为最小的。此时，q={1,3},p={1,2}。
下面出现了 -1。队尾元素 3 比 -1 大，那么意味着只要 -1 进队，那么 3 在其有生之年必定成为不了最小值，原因很明显：因为当下面 3 被框起来，那么 -1 也一定被框起来，所以 3永远不能当最小值。所以，3 从队尾出队。同理，1 从队尾出队。最后 -1 进队，此时q={-1},p={3}。
出现 -3。同上面分析，-1 > -3，-1 从队尾出队, -3 从队尾进队。q={-3}，p={4}。
出现 5。因为 5 > -3，同第二条分析，5在有生之年还是有希望的，所以 5 进队。此时，q={-3,5},p={4,5}。
出现 3。3 先与队尾的 5 比较，3 < 5，按照第 3 条的分析，5 从队尾出队。3 再与 -3 比较，同第二条分析，3 进队。此时，q={-3,3},p={4,6}。
出现 6。6 与 3 比较，因为 3 < 6，所以 3 不必出队。由于 3 以前的元素都＜3，所以不必再比较，6 进队。因为 -3 此时已经在滑动窗口之外，所以 -3 从队首出队。此时，q={3,6},p={6,7}。
出现 7。队尾元素 6 小于7，7 进队。此时，q={3,6,7},p={6,7,8}。
那么，我们对单调队列的基本操作已经分析完毕。因为单调队列中元素大小单调递(增 / 减 / 自定义比较)，因此，队首元素必定是最值。按题意输出即可。
[AcWing]154. 滑动窗口（C++实现）单调队列模板题_Cloudeeeee的博客-CSDN博客
Acwing算法基础课学习笔记(四)--数据结构之单链表&&双链表&&模拟栈&&模拟队列&&单调栈&&单调队列&&KMP_nullwh的博客-CSDN博客
#include<iostream>
using namespace std;
const int N = 1000010;
int n,k;
//存储原来的值 单调队列
int a[N],q[N];
int main()
{
scanf("%d%d",&n,&k);
//读入所有数
for(int i = 0;i < n;i++ ) scanf("%d",&a[i]);
//一开始队列为空 定义队头队尾
int hh = 0,tt = -1;
for(int i = 0;i < n;i++ )
{
//判断队头是否已经滑出窗口 直接用下标来判断-> 队列中存储的是下标 首先判断队列是否为空 起点是i - k + 1 终点是i
//每次窗口只会往后移动一位-> 每次队列中最多只有一个数不在窗口中的
if(hh <= tt && i - k + 1 >= q[hh]) hh++ ;
//不为空 如果新插入的数比队尾的数要小的话 就把队尾删除
while(hh <= tt && a[q[tt]] >= a[i]) tt-- ;
//把当前的下标插到队列中
q[ ++tt] = i;
//从前 k 个开始输出 数据不足 k 个就不用输出
if(i >= k - 1) printf("%d ",a[q[hh]]);
}
put("");
hh = 0,tt = -1;
for(int i = 0;i < n;i++ )
{
if(hh <= tt && i - k + 1 >= q[hh]) hh++ ;
while(hh <= tt && a[q[tt]] <= a[i]) tt-- ;
q[ ++tt] = i;
//队列由单调递增变成单调递减-> 队头还是最大值
if(i >= k - 1) printf("%d ",a[q[hh]]);
}
put("");
return 0;
}kmp 算法
先想一下暴力做法？如何去优化？
算法篇 --- BF算法(暴力匹配算法)_菜徐鸭的博客-CSDN博客
?s[ N ]：比较长的串，要匹配的串
p[ M ]：比较短的串，模板串
蓝色表示模板串
红色表示要匹配的串
kmp 的下标习惯从 1 开始?
第一重循环 i 枚举当前起点(假设从 s[i] 开始匹配 p，能不能匹配成功)，第二重循环从前往后枚举整个长度，flag 一 开始为 true 表示成功的状态，匹配过程中，如果有不匹配的情况出现(s[ i ] ！= p[ j ])，flag = false
假设匹配到中间的某个位置之前都是完全一样的，匹配到下一个字母就不一样了，暴力做法需要把整个模板串往后移动一位，重新开始匹配
其中隐含了一些额外的信息，如果可以利用这些额外信息，就可以帮助我们少枚举一些东西(从而不需要重新匹配)
假设匹配到中间的某一个位置失败了，需要重新开始匹配的模板串 最少往后移动到什么时候，可以继续匹配
图中两段绿色的线长度应该是一样长的，发现最少往后移动多少只和模板串有关，只要预处理出来前缀和后缀相等的最大值就是答案(相等的值越大，意味着往后移动的距离越少)
需要对模板串数组的每一个点预处理出前缀和后缀相等的长度，相等的前缀和后缀长度最大值是多少→ next 数组
next[ i ] 表示以 i 为中点的后缀和从 1 开始的前缀相等，而且后缀的长度最长
next 数组的含义：
匹配的过程：
假设从前往后匹配的时候，在 i 之前都是匹配的(si - 1 = pj)，从第 i 个点开始出现不匹配的情况：si ！= pj+1，此时需要把红色的线从前往后移动，看最少移动多少(直接调用 next[ j ]，最少移动的距离就是最大的后缀)
找到以当前点为终点的后缀和前缀最长是多少
移动之后的下标就是 next[ j ]，再看模式串的下一个点是否和 s[ i ] 匹配，如果不匹配，重复此过程，如果匹配就继续往下走
i 遍历 s 所有的字母， j 从 0 开始，每次试图往前移动，看能不能完全匹配，判断 j 能不能往下走：如果 j 不能往下走，j 就往前退一步 ( j = ne[ j ] )，如果 j 已经退无可退了还是没办法走，就看 si 的下一个位置；如果退到某一步之后下一步可以走了，就继续往下走. . .
求 next[ i ] 过程：
next数组的含义是：一个固定字符串的最长前缀和最长后缀相同的长度，并且长度小于(不能等于)固定字符串本身，使得当匹配失败我们让子串向后移动最少的距离使模板串可以继续匹配，也就是说在某个字符失配时，该字符对应的 next 值会告诉你下一步匹配中，子串应该跳到哪个位置
和匹配过程类似，需要求 next 数组的串为? p[ N ]，对于 i 而言，可以匹配的最大后缀和前缀是什么
j = ne[ j ]，假设到 i 这个点已经匹配成功了，当我们想匹配下一个位置的时候，j 不能再往后走了(停止了)，想看 j 下一次再重新匹配的时候，可以把 j 最少往后移动多少 (使得最大后缀和前缀相等)，就是 ne[ j ]
next[ 1 ] = 0，a 匹配失败应该从 0 开始，所以 i 应该从 2 开始，整个时间复杂度为 O( n )
KMP详细解释及KMP算法模板_zhbbbb！的博客-CSDN博客_kmp算法模板
#include<iostream>
using namespace std;
const int N = 10010,M = 100010;
int n,m;
//p 的长度是N,s长度是 M
char p[N],s[M];
//定义next数组
int ne[N];
int main()
{
//读入数据-> 下标从 1 开始
cin >> n >> p + 1 >> m >> s + 1;
//求 next 的过程 "abababab"
for(int i = 2,j = 0;i <= n;i++ )
{
//1.j = 0
//4.j = 0
//7.j = 1
while(j && p[i] != p[j + 1]) j = ne[i];
//2.p[2] != p[0 + 1]-> a != b
//5.p[3] == p[0 + 1]-> a == a-> j++
//8.p[4] == p[1 + 1]-> b == b-> j++
if(p[i] == p[j + 1]) j++;
//如果p[i] != p[j + 1],则出while循环的条件是j = 0, 说明没有前缀和后缀相同的长度,next[i]值也为0
//3.ne[2] = 0
//6.ne[3] = 1
//9.ne[4] = 2
ne[i] = j;
}
//kmp 匹配过程
//i枚举当前si
for(int i = 1,j = 0;i <= m;i++ )
{
//试图和 si 匹配的是 pj+1
//j 没有退回起点-> 如果 j 退回起点就需要重新开始匹配-> 绿色和红色圈不能匹配
//让红色线最少往后移动多少-> 最大的后缀等于前缀 直到匹配为止 或者 j 已经退无可退
while(j && s[i] != p[j + 1]) j = ne[j];
//如果已经匹配 j 移到下一个位置继续做匹配
if(s[i] == p[j + 1]) j++;
if(j == n)
{
//匹配成功
printf("%d ",i - n);
//匹配下一个
j = ne[j];
}
}
return 0;
}
