浅谈KMP算法(c++)

目录

  • 前缀函数
  • 应用
    • 【模板】KMP
      • 题目描述
      • 输入格式
      • 输出格式
      • 样例 #1
        • 样例输入 #1
        • 样例输出 #1
      • 提示
        • 样例 1 解释
        • 数据规模与约定
      • 思路
      • AC代码
    • 本质不同子串数
  • 例题讲解
    • [NOI2014] 动物园
      • 题目描述
      • 输入格式
      • 输出格式
      • 样例 #1
        • 样例输入 #1
        • 样例输出 #1
      • 提示
      • 思路
      • AC代码
    • [POI2006] OKR-Periods of Words
      • 题面翻译
      • 题目描述
      • 输入格式
      • 输出格式
      • 样例 #1
        • 样例输入 #1
        • 样例输出 #1
      • 思路
      • AC代码
  • [BOI2009] Radio Transmission 无线传输
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 提示
        • 样例输入输出 1 解释
        • 规模与约定
      • 思路
      • AC代码
    • [COCI2011-2012#4] KRIPTOGRAM
      • 题目描述
      • 输入格式
      • 输出格式
      • 样例 #1
        • 样例输入 #1
        • 样例输出 #1
      • 样例 #2
        • 样例输入 #2
        • 样例输出 #2
      • 样例 #3
        • 样例输入 #3
        • 样例输出 #3
      • 提示
      • 思路
      • AC代码

为方便讲述,字符串下标从 开始

前缀函数

给定一个长度为 n n n的字符串 s s s其前缀函数定义为一个长度为 n n n的数组 π \pi π, π i \pi_i πi 为子串 s [ 0 , 1 , … … i ] s[0,1,……i] s[0,1,……i]的所有相等的真前缀和真后缀(称为border)的最长长度,若没有则为.
朴素求解前缀函数

int n = (int)s.length();
vector<int> pi(n);
for (int i = 1; i < n; i++)
for (int j = i; j >= 0; j--)
if (s.substr(0, j) == s.substr(i - j + 1, j)) {pi[i] = j;break;
}

这显然是一个 n 3 n^3 n3的算法
我们可以通过一些观察来优化这个算法。

  1. π i + 1 ≤ π i + 1 \pi _{i+1} \leq \pi_i +1 πi+1πi+1 反证即可,假设 π i + 1 \pi_{i+1} πi+1更大,那 π i \pi_i πi也应该更大
    通过这个我们可以把原来的暴力优化成 但这还不够优秀
  2. 如果失配,我们可以利用之前已经处理过的信息来避免一些重复比较
    考虑我们当前已经处理完前 i i i为,且第 i + 1 i+1 i+1位失配,即 s i ≠ s π i + 1 s_i\neq s_{\pi_i+1} si=sπi+1,我们想快速找到最长的新匹配。
    由 border 的定义,也就是我们要找到最大的j使得 s i , j = s i = j + 1 , i s_{i,j}=s_{i=j+1,i} si,j=si=j+1,i^ s j + 1 = s i + 1 s_{j+1}=s_{i+1} sj+1=si+1
    只考虑第一个条件,事实上 j = π π i j=\pi_{\pi_i} j=ππi
    证明:
  3. π π i \pi_{\pi_i} ππi满足条件1 ,手模一下即可。
  4. π π i \pi_{\pi_i} ππi是最大的满足条件的,反证即可。
    通过以上两个观察,我们就可以得出最终的算法,也就是 KMP
for(int i = 2, j = 0; i <= n; ++i){
while(j && s[j + 1] != s[i])j = nxt[j];
if(s[j + 1] == s[i]) ++j;
nxt[i] = j;
}

时间复杂度由 while 循环计算,复杂度 O ( n ) O(n) O(n)

应用

字符串匹配

【模板】KMP

题目描述

给出两个字符串 s 1 s_1 s1 s 2 s_2 s2,若 s 1 s_1 s1 的区间 [ l , r ] [l, r] [l,r] 子串与 s 2 s_2 s2 完全相同,则称 s 2 s_2 s2 s 1 s_1 s1 中出现了,其出现位置为 l l l
现在请你求出 s 2 s_2 s2 s 1 s_1 s1 中所有出现的位置。

定义一个字符串 s s s 的 border 为 s s s 的一个 s s s 本身的子串 t t t,满足 t t t 既是 s s s 的前缀,又是 s s s 的后缀。
对于 s 2 s_2 s2,你还需要求出对于其每个前缀 s ′ s' s 的最长 border t ′ t' t 的长度。

输入格式

第一行为一个字符串,即为 s 1 s_1 s1
第二行为一个字符串,即为 s 2 s_2 s2

输出格式

首先输出若干行,每行一个整数,按从小到大的顺序输出 s 2 s_2 s2 s 1 s_1 s1 中出现的位置。
最后一行输出 ∣ s 2 ∣ |s_2| s2 个整数,第 i i i 个整数表示 s 2 s_2 s2 的长度为 i i i 的前缀的最长 border 长度。

样例 #1

样例输入 #1
ABABABC
ABA
样例输出 #1
1
3
0 0 1

提示

样例 1 解释

对于 s 2 s_2 s2 长度为 3 3 3 的前缀 ABA,字符串 A 既是其后缀也是其前缀,且是最长的,因此最长 border 长度为 1 1 1

数据规模与约定

本题采用多测试点捆绑测试,共有 3 个子任务

  • Subtask 1(30 points): ∣ s 1 ∣ ≤ 15 |s_1| \leq 15 s115 ∣ s 2 ∣ ≤ 5 |s_2| \leq 5 s25
  • Subtask 2(40 points): ∣ s 1 ∣ ≤ 1 0 4 |s_1| \leq 10^4 s1104 ∣ s 2 ∣ ≤ 1 0 2 |s_2| \leq 10^2 s2102
  • Subtask 3(30 points):无特殊约定。

对于全部的测试点,保证 1 ≤ ∣ s 1 ∣ , ∣ s 2 ∣ ≤ 1 0 6 1 \leq |s_1|,|s_2| \leq 10^6 1s1,s2106 s 1 , s 2 s_1, s_2 s1,s2 中均只含大写英文字母。

思路

对模式串跑 KMP,得到 数组ne,然后直接扫文本串匹配即可,若失配则跳 ,完全匹配时也跳 ,因为有可能两次出现有重叠的部分。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m,i,j;
char  p[N],s[N];
int ne[N];
int main(){scanf("%s%s",s+1,p+1);m=strlen(s+1);n=strlen(p+1);for(i=2,j=0;i<=n;i++){while(j&&p[i]!=p[j+1])j=ne[j];if(p[i]==p[j+1])j++;ne[i]=j;}for(i=1,j=0;i<=m;i++){while(j&&s[i]!=p[j+1])j=ne[j];if(s[i]==p[j+1])j++;if(j==n){printf("%d\n",i-n+1);j=ne[j];}}for(int i=1;i<=n;i++)printf("%d ",ne[i]);
}

本质不同子串数

给定长度为 n n n的字符串 s ,求本质不同子串数。考虑用递推的方法,令 s,求本质不同子串数。 考虑用递推的方法,令 s,求本质不同子串数。考虑用递推的方法,令 f i f_i fi s [ 1 , i ] s[1,i] s[1,i]的本质不同子串数,考虑如何算出 f i + 1 f_{i+1} fi+1新出现的子串显然只能是以 i + 1 i+1 i+1结尾的。
如果将字符串反转,就变成要计数以 i + 1 i+1 i+1开头且未出现过的子串。
我们可以反过来计数已经出现过的有多少个,考虑我们前缀函数求出了什么,每一个border都是一个以 i + 1 i+1 i+1开头的子串的出现。
所以出现过的一共有 π m a x \pi_{max} πmax个,新增的就是 i + 1 − π m a x i+1-\pi_{max} i+1πmax
这样我们就可以以 O ( 2 ) O(2) O(2)的复杂度求出本质不同子串数。
当然,还有更复杂的算法可以用更优秀的复杂度处理该问题,在此不表。

例题讲解

[NOI2014] 动物园

题目描述

近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决定开设算法班,让动物们学习算法。

某天,园长给动物们讲解 KMP 算法。

园长:“对于一个字符串 S S S,它的长度为 L L L。我们可以在 O ( L ) O(L) O(L) 的时间内,求出一个名为 n e x t \mathrm{next} next 的数组。有谁预习了 n e x t \mathrm{next} next 数组的含义吗?”

熊猫:“对于字符串 S S S 的前 i i i 个字符构成的子串,既是它的后缀又是它的前缀的字符串中(它本身除外),最长的长度记作 n e x t [ i ] \mathrm{next}[i] next[i]。”

园长:“非常好!那你能举个例子吗?”

熊猫:“例 S S S abcababc \verb!abcababc! abcababc,则 n e x t [ 5 ] = 2 \mathrm{next}[5]=2 next[5]=2。因为 S S S的前 5 5 5个字符为 abcab \verb!abcab! abcab ab \verb!ab! ab 既是它的后缀又是它的前缀,并且找不到一个更长的字符串满足这个性质。同理,还可得出 n e x t [ 1 ] = n e x t [ 2 ] = n e x t [ 3 ] = 0 \mathrm{next}[1] = \mathrm{next}[2] = \mathrm{next}[3] = 0 next[1]=next[2]=next[3]=0 n e x t [ 4 ] = n e x t [ 6 ] = 1 \mathrm{next}[4] = \mathrm{next}[6] = 1 next[4]=next[6]=1 n e x t [ 7 ] = 2 \mathrm{next}[7] = 2 next[7]=2 n e x t [ 8 ] = 3 \mathrm{next}[8] = 3 next[8]=3。”

园长表扬了认真预习的熊猫同学。随后,他详细讲解了如何在 O ( L ) O(L) O(L) 的时间内求出 n e x t \mathrm{next} next 数组。

下课前,园长提出了一个问题:“KMP 算法只能求出 n e x t \mathrm{next} next 数组。我现在希望求出一个更强大 n u m \mathrm{num} num 数组一一对于字符串 S S S 的前 i i i 个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作 n u m [ i ] \mathrm{num}[i] num[i]。例如 S S S aaaaa \verb!aaaaa! aaaaa,则 n u m [ 4 ] = 2 \mathrm{num}[4] = 2 num[4]=2。这是因为 S S S的前 4 4 4 个字符为 aaaa \verb!aaaa! aaaa,其中 a \verb!a! a aa \verb!aa! aa 都满足性质‘既是后缀又是前缀’,同时保证这个后缀与这个前缀不重叠。而 aaa \verb!aaa! aaa 虽然满足性质‘既是后缀又是前缀’,但遗憾的是这个后缀与这个前缀重叠了,所以不能计算在内。同理, n u m [ 1 ] = 0 , n u m [ 2 ] = n u m [ 3 ] = 1 , n u m [ 5 ] = 2 \mathrm{num}[1] = 0,\mathrm{num}[2] = \mathrm{num}[3] = 1,\mathrm{num}[5] = 2 num[1]=0,num[2]=num[3]=1,num[5]=2。”

最后,园长给出了奖励条件,第一个做对的同学奖励巧克力一盒。听了这句话,睡了一节课的企鹅立刻就醒过来了!但企鹅并不会做这道题,于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出 n u m \mathrm{num} num数组呢?

特别地,为了避免大量的输出,你不需要输出 n u m [ i ] \mathrm{num}[i] num[i] 分别是多少,你只需要输出所有 ( n u m [ i ] + 1 ) (\mathrm{num}[i]+1) (num[i]+1) 的乘积,对 1 0 9 + 7 10^9 + 7 109+7 取模的结果即可。

输入格式

1 1 1 行仅包含一个正整数 n n n,表示测试数据的组数。
随后 n n n 行,每行描述一组测试数据。每组测试数据仅含有一个字符串 S S S S S S 的定义详见题目描述。数据保证 S S S 中仅含小写字母。输入文件中不会包含多余的空行,行末不会存在多余的空格。

输出格式

包含 n n n 行,每行描述一组测试数据的答案,答案的顺序应与输入数据的顺序保持一致。对于每组测试数据,仅需要输出一个整数,表示这组测试数据的答案对 1 0 9 + 7 10^9+7 109+7 取模的结果。输出文件中不应包含多余的空行。

样例 #1

样例输入 #1
3
aaaaa
ab
abcababc
样例输出 #1
36
1
32

提示

测试点编号约定
1 n ≤ 5 , L ≤ 50 n \le 5, L \le 50 n5,L50
2 n ≤ 5 , L ≤ 200 n \le 5, L \le 200 n5,L200
3 n ≤ 5 , L ≤ 200 n \le 5, L \le 200 n5,L200
4 n ≤ 5 , L ≤ 10 , 000 n \le 5, L \le 10,000 n5,L10,000
5 n ≤ 5 , L ≤ 10 , 000 n \le 5, L \le 10,000 n5,L10,000
6 n ≤ 5 , L ≤ 100 , 000 n \le 5, L \le 100,000 n5,L100,000
7 n ≤ 5 , L ≤ 200 , 000 n \le 5, L \le 200,000 n5,L200,000
8 n ≤ 5 , L ≤ 500 , 000 n \le 5, L \le 500,000 n5,L500,000
9 n ≤ 5 , L ≤ 1 , 000 , 000 n \le 5, L \le 1,000,000 n5,L1,000,000
10 n ≤ 5 , L ≤ 1 , 000 , 000 n \le 5, L \le 1,000,000 n5,L1,000,000

思路

要求的就是每个前缀的 border 集合大小,并且满足这个 border 得是不大于字符串长度一半的。
首先给出一种暴力的做法,对于每一个前缀 s [ 1 : j ] s[1:j] s[1:j]都不断跳 next 指针,如果当前跳到 i i i的节点 满足其长度不超过 j 2 \frac{j}{2} 2j 那么就给 n u m j num_j numj加上1 。这个算法成立的原因是 border 的传递性:不断迭代 next 等价于遍历 border。
集合大小可以通过跳 next 的次数得到,也就是说我们可以记录一下从每个串出发不断跳next,能跳多少次,计为 c n t i cnt_i cnti ,那么有 c n t i = c n t n e x t i + 1 cnt_i=cnt_{next_i}+1 cnti=cntnexti+1 。其实也可以将 ( i , n e x t i ) (i,next_i) (i,nexti)建成一棵树,这棵树常被称为 b o r d e r border border树或是$ f a i l fail fail树。树上的深度也就代表着对应节点的 b o r d e r border border个数。
于是问题可以转化为对于每个 s [ 1 : i ] s[1:i] s[1:i]求满足条件的最长的 border s[1;j],之后给答案累乘上 c n t j + 1 cnt_j+1 cntj+1即可。
至于如何去求这个 j j j,首先给出一种基于分析的做法:
如果我们已经求出了 s [ 1 : i ] s[1 : i] s[1:i] j j j ,在这个基础上去求 s [ 1 : i + 1 ] s[1 : i + 1] s[1:i+1] 的满足条件的 k k k
直觉告诉我们,用与求 next 指针一样的方法去做就好了:不断去检查 s j + 1 s_{j+1} sj+1 是否与 s i + 1 s_{i+1} si+1相等。如果是那么 k = j + 1 k = j + 1 k=j+1,否则令 j = n e x t j j = next_j j=nextj并继续检测相等的过程。特别的,
最终如果发现 k > i + 1 2 k > \frac{i+1}{2} k>2i+1,那么令 k = n e x t k k = next_k k=nextk
根据与求 next 过程类似的分析可以发现,这个过程求出的 j 一定是一个合法的 border。
但是为什么一定是最大的?可以通过反证法证明,直接理解也并不困难。
另外给出一种看起来就很套路的做法:
问题可以转换到 border 树上。那么只需要对于每个前缀s[1 : i]求出border 树上 i 的祖先中长度满足条件 < i 2 <\frac{i}{2} <2i 的第一个并给答案累乘它的深度。
可以通过倍增来求解。预处理出 N e x t x , i Next_{x,i} Nextx,i表示从s[1 : x]跳 2 i 2^i 2i次 next 指针会跳到哪个节点。
对于每次询问i从大到小枚举二进制位,如果跳完之后还不满足 < i 2 <\frac{i}{2} <2i 就不断跳。这个过程与倍增求 lca 类似。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
char s[1000100];
int f[1000100], num[1000100];
int main() {int T;scanf("%d", &T);while (T--) {scanf("%s", s + 1);int n = strlen(s + 1);f[1] = 0;num[1] = 1;for (int i = 2, j = 0; i <= n; ++i) {	while (j && s[j + 1] != s[i]) j = f[j];if (s[j + 1] == s[i])f[i] = ++j;elsef[i] = 0;num[i] = num[j] + 1;}long long ans = 1;for (int i = 2, j = 0; i <= n; ++i) {while (j && s[j + 1] != s[i]) j = f[j];if (s[j + 1] == s[i]) ++j;if (j > i >> 1) j = f[j];ans = (ans * (num[j] + 1)) % mod;}printf("%lld\n", ans);}return 0;
}

[POI2006] OKR-Periods of Words

题面翻译

对于一个仅含小写字母的字符串 a a a p p p a a a 的前缀且 p ≠ a p\ne a p=a,那么我们称 p p p a a a 的 proper 前缀。

规定字符串 Q Q Q 表示 a a a 的周期,当且仅当 Q Q Q a a a 的 proper 前缀且 a a a Q + Q Q+Q Q+Q 的前缀。若这样的字符串不存在,则 a a a 的周期为空串。

例如 ababab 的一个周期,因为 ababab 的 proper 前缀,且 ababab+ab 的前缀。

求给定字符串所有前缀的最大周期长度之和。

题目描述

A string is a finite sequence of lower-case (non-capital) letters of the English alphabet. Particularly, it may be an empty sequence, i.e. a sequence of 0 letters. By A=BC we denotes that A is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.) of the strings B and C (in this order). A string P is a prefix of the string !, if there is a string B, that A=PB. In other words, prefixes of A are the initial fragments of A. In addition, if P!=A and P is not an empty string, we say, that P is a proper prefix of A.

A string Q is a period of Q, if Q is a proper prefix of A and A is a prefix (not necessarily a proper one) of the string QQ. For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string A is the longest of its periods or the empty string, if A doesn’t have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string.

Task Write a programme that:

reads from the standard input the string’s length and the string itself,calculates the sum of lengths of maximum periods of all its prefixes,writes the result to the standard output.

输入格式

In the first line of the standard input there is one integer k k k ( 1 ≤ k ≤ 1 000 000 1\le k\le 1\ 000\ 000 1k1 000 000) - the length of the string. In the following line a sequence of exactly k k k lower-case letters of the English alphabet is written - the string.

输出格式

In the first and only line of the standard output your programme should write an integer - the sum of lengths of maximum periods of all prefixes of the string given in the input.

样例 #1

样例输入 #1
8
babababa
样例输出 #1
24

思路

根据 border 与周期的关系,我们知道我们要求的就是每个前缀的最小 border。
对于S[1 : i] ,如果其最小的 border j满足 i − j ≥ i 2 i-j\geq \frac{i}{2} ij2i ,就可以为答案累计 。
根据迭代 next 遍历 border 集合的原理,我们可以对每个前缀s[1 : i]维护一个 m n i mn_i mni表示由i不断跳 next 所能得到的最小的非 0 border。
容易发现如果 n e x t i = 0 next_i=0 nexti=0,那么 m n i = i mn_i=i mni=i ,否则 m n i = m n n e x t i mn_i=mn_{next_i} mni=mnnexti
另外如果把本题放到 border 树上,可以发现这个要求的东西就是每个节点属于根节点(长度为 0 的前缀)的哪个子树。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
long long n,i,j;
char s[N];
long long ne[N],ans;
int main(){scanf("%d%s",&n,s+1);for(i=2,j=0;i<=n;i++){while(j&&s[i]!=s[j+1])j=ne[j];if(s[i]==s[j+1])j++;ne[i]=j;}for(i=2,j=2;i<=n;i++,j=i){while(ne[j])j=ne[j];if(ne[i])ne[i]=j;ans+=i-j;}cout<<ans<<endl;
}

[BOI2009] Radio Transmission 无线传输

题目描述

给你一个字符串 s 1 s_1 s1,它是由某个字符串 s 2 s_2 s2 不断自我连接形成的(保证至少重复 2 2 2 次)。但是字符串 s 2 s_2 s2 是不确定的,现在只想知道它的最短长度是多少。

输入格式

第一行一个整数 L L L,表示给出字符串的长度。

第二行给出字符串 s 1 s_1 s1 的一个子串,全由小写字母组成。

输出格式

仅一行,表示 s 2 s_2 s2 的最短长度。

样例 #1

样例输入 #1

8
cabcabca

样例输出 #1

3

提示

样例输入输出 1 解释

对于样例,我们可以利用 abc \texttt{abc} abc 不断自我连接得到 abcabcabcabc \texttt{abcabcabcabc} abcabcabcabc,读入的 cabcabca \texttt{cabcabca} cabcabca,是它的子串。

规模与约定

对于全部的测试点,保证 1 < L ≤ 1 0 6 1 < L \le 10^6 1<L106

思路

本题考查的是对next数组的理解,其实答案就是n-ne[n]

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m,i,j;
char  p[N],s[N];
int ne[N];
int main(){scanf("%d%s",&n,p+1);for(i=2,j=0;i<=n;i++){while(j&&p[i]!=p[j+1])j=ne[j];if(p[i]==p[j+1])j++;ne[i]=j;}printf("%d\n",n-ne[n]);
}

[COCI2011-2012#4] KRIPTOGRAM

题目描述

现有一段明文和一部分密文。明文和密文都由英文单词组成,且密文中的一个单词必然对应着明文中的一个单词。

求给出的密文在明文中可能出现的最早位置。

输入格式

第一行,若干个英文单词和一个 $\texttt $$,表示明文。

第二行,若干个英文单词和一个 $\texttt $$,表示密文。

每行末尾的 $\texttt $$ 用于表示该行结束。数据保证没有多个 $\texttt $$ 出现在同一行的情况。

输出格式

输出密文在明文中可能出现的最早位置,即密文的第一个单词在明文中可能出现的最早位置。

样例 #1

样例输入 #1
a a a b c d a b c $
x y $
样例输出 #1
3

样例 #2

样例输入 #2
xyz abc abc xyz $
abc abc $
样例输出 #2
2

样例 #3

样例输入 #3
a b c x c z z a b c $
prvi dr prvi tr tr x $
样例输出 #3
3

提示

【数据规模与约定】

  • 对于 100 % 100\% 100% 的数据,明文和密文所对应字符串的长度不超过 1 0 6 10^6 106,输入的单词均由小写字母组成。

【提示与说明】

题目译自 COCI 2011-2012 CONTEST #4 Task 6 KRIPTOGRAM

本题分值按 COCI 原题设置,满分 140 140 140

思路

在传统的 KMP 算法中,我们直接比较字符之间是否相等。

针对此题的情况,只需要把判断式换成i - preA[i]== j - preB[j] || ! preB[j] && preA[i] <= i - j就行

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
string a[N], b[N];
int lena, lenb;
int sp_len[N], prea[N], preb[N];
void getPre(string str[], int pre[], int length) {unordered_map<string, int> last_pos;for (int i=1;i<=length;i++) {pre[i]=last_pos[str[i]];last_pos[str[i]]=i;}
}
void getSpLen() {int i=2,j=1;while (i<=lenb) {if(i-preb[i]==j-preb[j]||!preb[j]&&preb[i]<=i-j)sp_len[i++]=j++;else if(j>1)j=sp_len[j-1]+1;else i++;}
}
int main() {string x;while (cin>>x,x!="$")a[++lena]=x;while (cin>>x,x!="$")b[++lenb]=x;getPre(a,prea,lena);getPre(b,preb,lenb);getSpLen();int i=1,j=1;while (i<=lena) {if(i-prea[i]==j-preb[j]||!preb[j]&&prea[i]<=i-j)i++, j++;else if(j>1)j=sp_len[j-1]+1;else i++;if(j>lenb){cout<<i-lenb<<endl;return 0;}}cout<<-1<<endl;return 0;
}

这是我的第十九篇文章,如有纰漏也请各位大佬指正
辛苦创作不易,还望看官点赞收藏打赏,后续还会更新新的内容。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/390099.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

智慧水务项目(一)django(drf)+angular 18 通过pycharm建立项目

一、环境准备 windows 10 pycharm python3.11 二、pycharm 创建django项目 三、建立requirements.txt 在根目录创建requirements.txt,也就是与manage.py同一目录下&#xff0c;先放下面几个依赖 Django djangorestframeworkpip install -r .\requirements.txt 更新下pip python…

ShardingSphere实战(1)- 分库分表基础知识

一、为什么要分库分表 分库分表是一种数据库优化策略&#xff0c;主要用于解决大型应用或高并发场景下数据库性能瓶颈的问题。具体来说&#xff0c;分库分表可以带来以下好处&#xff1a; 提高性能&#xff1a; 减少单个数据库实例的负载&#xff0c;避免单点性能瓶颈。当数据…

【香橙派系列教程】(五)Linux的热拔插UDEV机制

【五】Linux的热拔插UDEV机制 在上一篇中我们发现&#xff0c;当手机接入开发板时&#xff0c;系统并不认识&#xff0c;当我们在/etc/udev目录下创建一个规则后&#xff0c;就可以通过adb访问到手机了&#xff0c;这里到底是怎么回事&#xff1f; 文章目录 【五】Linux的热拔插…

武汉流星汇聚:亚马逊平台消费者众多,助力中国卖家销售额大幅增长

在全球电商的浩瀚星空中&#xff0c;亚马逊凭借其庞大的消费者规模和强大的市场影响力&#xff0c;为无数商家特别是中国卖家提供了前所未有的发展机遇。近年来&#xff0c;越来越多的中国卖家选择通过亚马逊平台&#xff0c;将优质产品直接送达全球消费者的手中&#xff0c;并…

精选3款国内wordpress 主题,建站首选

WordPress作为一款功能强大且易于使用的建站平台&#xff0c;已经成为了许多企业和个人搭建网站的首选。为了帮助大家更好地选择适合自己的WordPress主题&#xff0c;小编将为大家推荐三款国内优秀的WordPress主题&#xff1a;子比主题、OneNav主题和RiTheme主题。 1.子比主题…

JavaScript ES6语法详解(下)

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;我是码喽的自我修养&#xff01;今天给大家分享JavaScript ES6语法详解(下)&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到带大家&#xff0c;欢迎收藏关注…

Qt Creator 与 ESP-IDF QEMU 模拟器使用指南

标题: Qt Creator 与 ESP-IDF QEMU 模拟器使用指南 概要: 本文为开发者提供了使用 Qt Creator 和 ESP-IDF QEMU 模拟器进行 ESP32 开发的详细指南&#xff0c;包括环境准备、项目创建和编译、模拟器设置、编程和调试等方面的内容。通过本指南&#xff0c;可以快速上手 Qt Crea…

Learning vtkjs之Calculator

过滤器 公式计算器 Calculator 介绍 The Calculator filter is a fast way to add derived data arrays to a dataset. These arrays can be defined over points, cells, or just field data that is “uniform” across the dataset (i.e., constant over all of space). Va…

手把手教你实现日期类

目录 前言 1.头文件的实现 2.日期类函数各项功能实现 2.1 初始化和打印&#xff08;比较简单&#xff09; 2.2日期大小判断 2.3日期的加减运算 3.日期类的输入输出 4.测试代码参考 结束语 前言 前面我们讲解了类的对象的大部分知识&#xff0c;例如拷贝构造&#xff0c…

优化数据处理效率,解读 EasyMR 大数据组件升级

EasyMR 作为袋鼠云基于云原生技术和 Hadoop、Hive、Spark、Flink、Hbase、Presto 等开源大数据组件构建的弹性计算引擎。此前&#xff0c;我们已就其展开了多方位、多角度的详尽介绍。而此次&#xff0c;我们成功接入了大数据组件的升级和回滚功能&#xff0c;能够借助 EasyMR …

乐乐音乐Kotlin版

简介 乐乐音乐Kotlin版&#xff0c;主要是基于ExoPlayer框架开发的Android音乐播放器&#xff0c;它支持lrc歌词和动感歌词(ksc歌词、krc歌词、trc歌词、zrce歌词和hrc歌词等)、多种格式歌词转换器及制作动感歌词、翻译歌词和音译歌词。 编译环境 Android Studio Jellyfish | …

canvas-视频绘制

通过Canvas元素来实时绘制一个视频帧&#xff0c;并在视频帧上叠加一个图片的功能可以当作水印。 获取Canvas元素&#xff1a; let canvas document.getElementById(canvas) 通过getElementById函数获取页面中ID为canvas的Canvas元素&#xff0c;并将其存储在变量canvas中。 …

【C++】C++11(可变参数模板、lambda表达式、包装器)

文章目录 1. 可变参数模板1.1 介绍1.2 emplace系列接口实现 2. lambda表达式2.1 语法介绍2.2 原理 3. 包装器4. bind 1. 可变参数模板 1.1 介绍 可变参数我们在C语言阶段已经了解过了&#xff0c;C语言中叫做可变参数列表&#xff0c;其中使用 ... 代表可变参数。 C语言中的可…

【给嵌入式新人的几条建议(共勉):三-C语言基础怎么补?】

给嵌入式新人的几条建议&#xff08;共勉&#xff09;&#xff1a;三-C语言基础怎么补&#xff1f; 前言1、先回答一个问题&#xff0c;对C语言的害怕到底在哪&#xff1f;&#xff08;纠正认知&#xff09;2、C语言基础&#xff0c;要补全部吗&#xff1f;No2.1 先看下自己属于…

企业个人信息安全保护实践

在数字化浪潮的推动下&#xff0c;个人信息安全问题日益凸显&#xff0c;企业如何在合规的框架下保护个人信息安全&#xff0c;成为了一项重要课题。结合国家标准的个人信息合规审计要求&#xff0c;以下为企业个人信息安全保护的最佳实践路径。 一、构建合规的个人信息保护体…

【文件解析漏洞】

使用windows2003sever服务器 第一个&#xff1a;目录解析 1、打开网站目录&#xff0c;右键打开资源管理器 新建一个1.asp文件 在1.asp目录下新建一个2.txt&#xff0c;输入asp的语句 2、使用本机访问windows2003的IP地址 访问http://192.168.189.155/1.asp/2.txt即可 第…

论文翻译:Large Language Models in Education: Vision and Opportunities

Large Language Models in Education: Vision and Opportunities 文章目录 教育中的大型语言模型&#xff1a;愿景与机遇摘要1 引言2. 教育与LLMsA. 教育背景B. LLMs背景C. 智能教育D. 教育中的LLMs 3. EduLLMs的关键技术4. LLM赋能教育A. LLMs在教育中的应用B. LLMs下教育的特…

Netty4自学笔记 (3) - Netty NIO Server和Client 样例说明

全文详见个人独立博客&#xff1a;Netty4自学笔记 (3) - Netty NIO Server和Client 样例说明 Netty4自学笔记 (3) - Netty NIO Server和Client 样例说明更新节奏缓慢&#xff0c;因为每晚学习注意力不够集中&#xff0c;学习进展缓慢。本还给自己找了一大堆其他理由&#xff0…

适用于个人使用的十大数据恢复工具:综合指南

有许多数据恢复工具和软件可用于帮助恢复丢失或损坏的文件。通过了解您的需求并考虑这里探讨的工具&#xff0c;您将能够选择最佳的数据恢复软件&#xff0c;并希望找回您丢失的宝藏。在本综合指南中&#xff0c;我们将探索个人使用的十大数据恢复工具&#xff0c;重点介绍它们…

自定义CustomRatingBar控件

通过自定义RatingBar的样式实现⭐️⭐️⭐️指示器的方式功能过于受限&#xff0c;而且显示的样式阴影会受到影响。 系统自带显示&#xff1a; 自定义样式&#xff1a; 因此简单自一个符合要求的 CustomRatingBar 支持设置星星数量支持设置星星Rating(float)支持设置空显示…