- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
先给出公式 ans = n - LPS[n-1] 。
其中ans为最小周期,n为给出的由假设的周期字符串中提取出的子串长度,LPS为前缀函数,n-1为字符串最后的位置下标 。
证明如下 证明ans = n - LPS[n-1],思路: (1) 证明特殊情况,即先对完整周期字符串进行证明,这时候的字符串组成是 [1][2][3][4] ,即4个周期拼接,所以由前缀函数的定义,有 。
[1][2][3] = [2][3][4],所以LPS[n-1] = 3*T,即三个周期,则ans = n(即4*T) - LPS[n-1] = 4*T - 3*T = T;
对于完整周期子串显然成立.
(2) 证明一般情况,即证明非完整周期字符串,假设给出的字符串是 [末部分][1][2][3][前部分] ,即中间有完整的周期,两边是不确定长度的,可能为0. 。
(为了方便,此处取[末部分] = [e],[前部分] = [b]) 。
1,当len([e]) = len([b]) = 0时,即(1)的情况,显然成立.
2,当len([e]) = 0,len([b]) != 0时此时字符串为 [1][2][3][b],由于[b]是周期的一部分,则[3]中包含[b],有
[1][2][b] = [2][3][b],此时 LPS[n-1] = 2*T + len([b]), n = 3*T + len([b]),显然有
ans = n - LPS[n-1] == 3*T + len([b]) - 2*T - len([b]) = T,成立.
3,当len([b]) = 0,len([e]) != 0时同理.
4,当len([e]) != 0,且len([b]) != 0时,此时字符串为 [e][1][2][3][b],根据2,3,有
[e][1][2][b] = [e][2][3][b],符合前缀函数定义,此时LPS[n-1] = 2*T + len([b+e]),n = 3*T + len([b+e])
显然有ans = n - LPS[n-1] = T,得证
5,当[e][b]内部没有完整的周期时,显然[e][b]可以自己组成最小周期,此时的LPS[n-1] = 0,ans = len([e+b]),为自己,得证
附上例题加以理解: 1,KMP算法模板https://www.luogu.com.cn/problem/P3375 2,字符串周期模板题https://www.luogu.com.cn/problem/P4391 。
例题1代码解析
//背景:刚学LPS函数及其应用KMP,先来道模板题练习,结果发现细节多
//注意:以后我的所有关于KMP的算法的字符串下标均是从0开始(便于与OI-wiki统一,好记忆)
//原理:KMP匹配字符串
//时间复杂度:o(n+m)
#include <bits/stdc++.h>
using namespace std;
void Prefixion(int LPS[],string s)//求生成字符串的前缀函数
{
LPS[0] = 0;//初始化前缀
for (int i = 1,big = s.size();i<big;i++)//遍历字符串
{
int j = LPS[i-1];//获取上一个位置的LPS
while(j>0&&s[j] != s[i]) j = LPS[j-1];//寻找第一个使得当前位置i的前缀性质仍满足的j
if(s[j] == s[i]) j++;//如果是因为相等退出循环的,j是位置,那么长度为j+1
LPS[i] = j;//记录当前位置的LPS
}
}
void KMP()//KMP算法
{
string text,pattern;
cin>>text>>pattern;//输入文本字符串及模板字符串(待查找的字符串)
string cur = pattern + '#' + text;//生成新的字符串
int s1 = pattern.size();//计算模板字符串的长度
int s2 = text.size();//计算文本字符串的长度
int LPS[s2+s1+1];//注意这里LPS的数组大小,如果开小了退不出函数(我也不知道为什么)
Prefixion(LPS,cur);//求生成字符串的前缀函数
vector<int> occurrence;//记录文本字符串匹配成功的起始位置
for (int i = s1+1;i<=s2+s1;i++)//从生成字符串的文本位置开始遍历
{
if(LPS[i] == s1) occurrence.push_back(i-2*s1);//如果满足当前情况,即记录下成功匹配的位置(相对文本):当前位置 - 2*模板长度
}
for (auto v:occurrence) cout<<v+1<<"\n";//依次输出位置(相对文本的)
for (int i = 0;i<s1;i++) cout<<LPS[i]<<" ";//输出每个前缀的函数值
cout<<"\n";
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
while(t--)
{
KMP();
}
return 0;
}
例题2代码解析
//背景:字符串的周期性问题,一开始不太理解,后来看了题解自己画图推导出来了
//本题题意:本题给出的是重复拼接字符串子串,求最小周期,也就是说假定了原字符串是周期函数,给分析证明提供了思路
//公式:ans = n - LPS[n-1]
#include <bits/stdc++.h>
using namespace std;
void Prefixion(int LPS[],string s)//前缀函数
{
LPS[0] = 0;//不要忘了初始化
for (int i = 1;s[i] != '\0';i++)
{
int j = LPS[i-1];
while(j > 0&&s[j] != s[i]) j = LPS[j-1];
if(s[j] == s[i]) j++;
LPS[i] = j;
}
}
void Solve()
{
int n;
string s;
cin>>n;//输入子串长度
cin>>s;//输入字符串
int LPS[n];//定义前缀函数
Prefixion(LPS,s);//求前缀函数
cout<<n - LPS[n-1]<<"\n";//输出最小周期
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
while(t--)
{
Solve();
}
return 0;
}
/*证明ans = n - LPS[n-1],思路:
(1)证明特殊情况,即先对完整周期字符串进行证明,这时候的字符串组成是 [1][2][3][4] ,即4个周期拼接,所以由前缀函数的定义,有
[1][2][3] = [2][3][4],所以LPS[n-1] = 3*T,即三个周期,则ans = n(即4*T) - LPS[n-1] = 4*T - 3*T = T;
对于完整周期子串显然成立.
(2)证明一般情况,即证明非完整周期字符串,假设给出的字符串是 [末部分][1][2][3][前部分] ,即中间有完整的周期,两边是不确定长度的,可能为0.
(为了方便,此处取[末部分] = [e],[前部分] = [b])
1,当len([e]) = len([b]) = 0时,即(1)的情况,显然成立.
2,当len([e]) = 0,len([b]) != 0时此时字符串为 [1][2][3][b],由于[b]是周期的一部分,则[3]中包含[b],有
[1][2][b] = [2][3][b],此时 LPS[n-1] = 2*T + len([b]), n = 3*T + len([b]),显然有
ans = n - LPS[n-1] == 3*T + len([b]) - 2*T - len([b]) = T,成立.
3,当len([b]) = 0,len([e]) != 0时同理.
4,当len([e]) != 0,且len([b]) != 0时,此时字符串为 [e][1][2][3][b],根据2,3,有
[e][1][2][b] = [e][2][3][b],符合前缀函数定义,此时LPS[n-1] = 2*T + len([b+e]),n = 3*T + len([b+e])
显然有ans = n - LPS[n-1] = T,得证
5,当[e][b]内部没有完整的周期时,显然[e][b]可以自己组成最小周期,此时的LPS[n-1] = 0,ans = len([e+b]),为自己,得证
码字不易,多多支持.
最后此篇关于KPM算法求字符串的最小周期证明的文章就讲到这里了,如果你想了解更多关于KPM算法求字符串的最小周期证明的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
(这不是关于定理证明,而是关于实践中的测试,例如 quickCheck) 让f一些通用函数 f :: RESTRICTIONS => GENERICS 具有一些“理想的”属性(即不是 hack,是不可
给定数组 arr 和索引数组 ind,以下算法就地重新排列 arr 以满足给定的索引: function swap(arr, i, k) { var temp = arr[i]; arr[i]
我有兴趣创建一个具有运行时间和空间限制的简单数组问题。看来我找到了解决问题的方法。请阅读以下java代码中问题的初始描述注释: /* * Problem: Given two integer ar
我是 isabelle 的新手,并试图证明以下简单的不等式: lemma ineq: "(a::real) > 0 ⟹ a 0 ⟹ b 0" proof have "1/a + 1/b >
是否有任何理论说缓存应该比文件系统更快? 我认为,由于文件系统也使用缓存,因此没有科学证据表明当文件系统的概念有些松散时,我们应该将内容从文件系统移动到诸如 memcache 之类的缓存中——比如下载
我正在做一个证明,我的一个子目标看起来有点像这样: Goal forall (a b : bool) (p: Prop) (H1: p -> a = b) (H2: p), neg
我有定义的归纳类型: Inductive InL (A:Type) (y:A) : list A -> Prop := | InHead : forall xs:list A, InL y (co
我知道 CRC 是一个线性函数,这意味着 CRC(x xor y) = CRC(x) xor CRC(y),但我不知道如何证明 CRC 的这个属性。 有谁有想法吗? 非常感谢! 最佳答案 这通常不是真
我是 Coq 的初学者。 虽然计算机为我验证了证明令人满意,但众所周知,满足 Coq 的证明对人类来说难以阅读。这是一个简单的例子,假设您没有看到任何评论: Theorem add_comm : fo
我试图了解是什么决定了类型参数是否必须是标称的。 虽然 GADT 和类型家族在某种意义上看起来不同,但它们不是“简单容器”,因为它们的实例定义可以“查看”它们的参数,但简单类型是否可以明显需要名义参数
我想使用 function 关键字定义来证明函数定义的正确性。以下是自然数的通常归纳定义上的加法函数的定义: theory FunctionDefinition imports Main begin
我定义了一个 Sygma-Type,如下所示: { R : nat -> nat -> bool | Reflexive R } 我有两个元素 r1 r2 : { R : nat -> nat ->
我有以下数据: new_pairs x y Freq start.latittude start.longitude start.station end.la
出于教育目的,我一直试图通过使用各种语言扩展和单例类型,在 Haskell 中重建《Type-Driven Development with Idris》(即 RemoveElem.idr )一书中的
我定义了一个 Sygma-Type,如下所示: { R : nat -> nat -> bool | Reflexive R } 我有两个元素 r1 r2 : { R : nat -> nat ->
我正在使用Ax DevTools,并且试图弄清楚如何使用相同的构建信息标记多个扫描。现在,我的测试运行如下: class MyTestCase : XCTestCase { func myTest
我正在尝试证明一个函数的正确性,该函数检查数组是否按递增/递减顺序排序或未排序。行为是返回 -1,如果按降序排序,1,如果按升序排序,大小为 1,或包含相同的值,0,如果没有已排序或为空。运行:Fra
我试图证明 Z3(Microsoft 的 SMT 求解器)中的一个归纳事实。我知道 Z3 通常不提供此功能,如 Z3 guide 中所述。 (第 8 节:数据类型),但是当我们限制要证明事实的域时,这
问题已编辑: 如代码中所述,HashSet 和 HashMap 是快速失败的(但这不是保证): void goHashSet() { Set set = new HashSet();
我试图使导航栏中的链接延伸到导航栏的全长。我环顾四周,发现了一些有用的信息,但无法使其正常工作 HTML: To
我是一名优秀的程序员,十分优秀!