lisl1233

字符串

最小生成树(2) 最短路径(5)

/ 注册

全部文章 / 字符串（共6篇）

最大回文子串--Manacher

最大回文子串----Manacher 思路：先把原字符串扩充然后遍历扩充后的数组用maxx存放最大回文长度 len数组存放他每个下标的的会问长度时间复杂度O(n) Code： #include<iostream> #include<cmath> #include<...

2021-07-16

1 357

最大连续子段和

最大连续子段和思路：用两个变量一个存放累计最大值一个存放当前和如果当前和小于0 则在这之前的数都pass掉给当前和重新赋值时间复杂度O(n) code: #include<iostream> #include<cmath> using namespace st...

2021-07-16

1 353

最长公共子序列--LCS

最长公共子序列----LCS 思路：普普通通动态规划并且判断他当前的取值是上方还是左方，并做好标记，再利用回溯，输出字符串时间复杂度O(nlogn) Code: #include<iostream> #include<cmath> #include<string....

2021-07-16

1 374

最大上升子序列--LIS

最大上升子序列思路：建立一个low数组，用于存放上升的子序列，并记录长度，如果一个数大于low的最后一个数，则将他添加到low数组最后面，如果不大于，则将那个数利用二分放在low合适的位置，以便下次比较。时间复杂度O(nlogn) Code： #include<iostream> ...

2021-07-16

1 381

字符串匹配--hash

字符串匹配--hash 思路：先算出母串的hash值，再算出子串的hash值，利用差分的思想，计算出母串长度与子串长度相等的hash值，并进行判断，如果hash值相等，即可判断他们为相同的字符串，如果担心hash值冲突，即可加以一层判断来保证结果的准确性时间复杂度O(n) Code： #inc...

2021-07-14

1 434

字符串匹配--KMP

字符串匹配思路： nxt[j]=k的意思是，下标为j的字符前字符串的最长相等前后缀为k nxt数组的值只与子串有关 nxtv则是优化nxt 使得处理时间更加短时间复杂度O(n) Code: #include<iostream> #include<memory.h> ...

2021-07-14

1 371