首页 > 其他分享 >字符串学习笔记(一)

字符串学习笔记(一)

时间:2023-04-06 20:56:48浏览次数:34  
标签:nxt int 笔记 next 学习 prefix 字符串 Border

一些定义:
1. Border: 如果一个字符串的某个前缀同与它长度相同的后缀完全相同,就称这个前缀(后缀)是这个字符串的一个Border.
2. 周期:如果一个字符串s满足对于任意的p < i \(\leqslant\) |s|, s[i] = s[i - p], 则称p是字符串s的周期,一个字符串可能有很多个周期。
3. 循环节:在周期的概念中,字符串末尾可能有未尽的循环单元,但是在循环节的概念中,必须每个循环单元都是完整的,即p | \(\lvert s \rvert\)(p整除字符串的长度),循环节是每个循环单元的长度。

重要性质:
1. 如果p是s的周期, 那么[1, |s| - p]是s的一个Border
证明: p是s的周期,那么s[i] = s[i + p];
[1, q]是s的一个Border, 那么s[1] = s[|s| - q + 1], s[2] = s[|s| - q + 2] \(\dots\) s[q] = s[|s|];
就是说 |s| - q + i = i + p => q = |s| - p;
这样的话,求周期和求Border的问题就可以相互转化。
2. s的Border的Border也是s的Border;
证明:稍微想一下就行了。

Border的求法:
要求所有的Border,只要求出所有前缀的最大Border就可以了。
设next[i] = prefix[i]的最大非平凡Border
很明显,next[1] = 0;
然后,考虑所有prefix[i]所有长度不为1的Border,任意一个,在减去一个字符以后都会是prefix[i - 1]的前缀。
那么我们在求prefix[i]的最大Border的时候,就依次看next[i - 1], next[next[i - 1]]..0, 检查后一个字符是否相等;
时间复杂度O(n),用势能分析法可以估算出来。

CODE:

void init(string & s) {
	nxt[1] = 0;
	for(int i = 2; i <= s.size() - 1; i ++) {
		nxt[i] = nxt[i - 1];
		while(nxt[i] && s[nxt[i] + 1] != s[i]) nxt[i] = nxt[nxt[i]];
		nxt[i] += (s[i] == s[nxt[i] + 1]);
	}
}

KMP:
首先贴一个朴素版本的代码

bool brute(string & s1, string & s2) {
	int n = s1.size() - 1;
	int m = s2.size() - 1;
	bool vis;
	for(int i = 1;  i <= n - m + 1; i ++) {
		vis = true;
		for(int j = 1; j <= m; j ++) {
			if(s2[j] != s1[i + j - 1]) vis = false;
		}
		if(vis) return true;
	}
	return false;
}

可以看到,在每次匹配失败以后,i指针只会后移一位,这太蠢了。
我们可以每次移动一个更合理的距离。
不太好说,可以找网上很经典的图,总之是枚举nxt[j],nxt[nxt[j]]就可以了。

标签:nxt,int,笔记,next,学习,prefix,字符串,Border
From: https://www.cnblogs.com/zuotihenkuai/p/17294125.html

相关文章

  • # Java笔记(12) 静态代理
    静态代理可以在不改变原有代码的情况下,增加新的功能和操作,对原有对象进行扩展。静态代理要求真实对象和代理对象都实现同一个接口,由代理对象代理真实角色的接口实现,并在实现前后增加新的操作。publicclassStaticProxy{publicstaticvoidmain(String[]args){Person......
  • vue3创建项目笔记
    E:\vue3学习>npminitvite@latestvite-blog----templatevueNeedtoinstallthefollowingpackages:[email protected]?(y)yScaffoldingprojectinE:\vue3学习\vite-blog...Done.Nowrun:cdvite-blognpminstallnpmrundevnpmnotice......
  • SQLlabs less1-10通关笔记
    SQLlabs通关笔记mysql数据结构在练习靶场前我们需要了解以下mysql数据库结构,mysql数据库5.0以上版本有一个自带的数据库叫做information_schema,该数据库下面有两个表一个是tables和columns。tables这个表的table_name字段下面是所有数据库存在的表名。table_schema字段下是所......
  • 机器学习数学基础之信息论
    信息论背后的原理是:从不太可能发生的事件中能学到更多的有用信息。发生可能性较大的事件包含较少的信息发生可能性较小的事件包含较多的信息独立事件包含额外的信息对于事件\(\mathbfx=x\),定义自信息self-information为:\[I(x)=-\logP(x)\]自信息仅仅处理单个输出。如果......
  • c++字符串拆分
    1staticvoidSplitString(conststring&data,conststring&delim,2std::vector<string>*result){3std::string::size_typepos;4constintsize=data.size();56for(intindex=0;index<size;++index)......
  • 快速学习反假币教程(仅供交流使用)
    仅供交流使用,如有侵权请联系[email protected] 反假币跳过十五分钟(仅供交流使用)以edge浏览器为例1.打开edge浏览器输入:http://wechat.renzhenwh.com/studyExam/examLogin2.按电脑F12打开开发者工具3.在edge上输入账号密码登录4.查看开发者工具,进行如下操作,复制Cookie后......
  • WPF的控件字符串内容使用StringFormat进行字符串转换
    在WPF中TextBlock的Text有时内容只需要改变个别数字,而不需要所以内容都修改,这时候就要使用StringFormat, 如:<TextBlockText="Ihavexxxfriends"/>这里面的xxx是个变量,那在Binding时应该怎样写呢<TextBlockText="{BindingFirendNumber,StringFormat='Ihave{0}firends......
  • 船舶的布局问题学习
    船舶的布局问题学习​ 船舶的布局问题包括许多小的布局类问题,包括船舶机舱设备的布局问题、船舶管路的布局问题、船舶舱室内属具的布局问题和船舶舱室划分布局问题等。船舶机舱设备的布局问题​ 船舶机舱设备布局设计属于密闭有限空间多目标优化设计问题,作为船舶的心脏,机舱设备......
  • Java笔记(11) 多线程
    Java原生支持多线程,主要通过以下四种方式实现多线程:继承Thread类实现Runnable接口实现Callable接口线程池继承Thread类通过创建Thread类的子类,并重写run()方法,通过调用start()方法启动线程。publicclassTestThreadextendsThread{@Overridepublicvoidru......
  • 2023.4.6学习记录
    p15神经网络_卷积层importtorchimporttorchvisionfromtorchimportnnfromtorch.nnimportConv2dfromtorch.utils.dataimportDataLoaderfromtorch.utils.tensorboardimportSummaryWriter#准备测试集dataset=torchvision.datasets.CIFAR10("dataset",train=False,......