12-数据结构-2
数据结构-2
栈
本身是个关于时间变量的大根堆，用来撤回
单调栈
找左右第一个小于的是递增栈，小于号朝向欲push的元素，大于的是递减栈，大于号朝向欲push的元素
- 左边第一个，从左到右top幸存者是淘汰者的答案，意味着下一层是其上一层的答案，从右到左淘汰者是top被淘汰者的答案，
- 右边第一个，从右到左top幸存者是淘汰者的答案，意味着下一层是其上一层的答案，从左到右淘汰者是top被淘汰者的答案
同向幸存者，反向淘汰者
队列
本身是个关于时间变量的小根堆，用来排队
维护左，枚举右
当不允许重复使用同一个数时，即用完把元素从数组删去时，只在没满足条件时进行计数，同时满足条件时对对应的数进行减数
Manacher
预处理后的串索引中心idx映射到原串的字符串区间:
原回文串长度 = 回文半径 - 1
void solve(string s) { int n = s.size();
string str(2 * n + 3, '#'); str[0] = '$'; for (int i = 0; i < n; ++i) { str[2 * i + 2] = s[i]; } str[2 * n + 2] = '^';
vector<int> plen(2 * n + 3); int boxR = 0, boxM = 0; for (int i = 2; i < 2 * n + 1; ++i) { int pl = 1;
if (i < boxR) { pl = min(plen[2 * boxM - i], boxR - i); }
while (str[i - pl] == str[i + pl]) { ++pl; }
if (i + pl > boxR) { boxR = i + pl; boxM = i; }
// 求最长回文子串，或者回文子串数量
plen[i] = pl; }}KMP
介绍
主要对象包括文本串和模式串，next数组。next数组可以从0编号或是从1编号，对应的模式匹配指针为-1和0，数组分为传统数组和next-val数组。前缀并不包括到最后一个字符，后缀并不包括到首个字符，所以单个字符串”a”是没有前后缀的，同时前后缀不能是整串，因为包括了最后一个字符和首个字符。
ABACABAB
求的是一整个子串的共同前后缀
加上最后一个字符后，前缀不再等于后缀，但是等于后缀的前缀，此时要找到后缀和某个真前缀相匹配的部分然后继续检验最后一个字符，也就是说要让后缀的后缀要和某个真前缀相同，即模式匹配，再检验下一个字符，看是不是相等前后缀，，因为左右部分是相同的，所以对左部分求最长共同前后缀就行了
-
pm[i]是1..i的最长共同前后缀长度
-
next[j]的意义为j位置失配时模式匹配指针j应该跳转到的位置
-
在串从0开始编号时，next[i] = pm[i - 1]然后补-1，可以理解为1..i-1的的最长共同前后缀长度
-
在串从1开始编号时，next[i] = pm[i - 1] + 1然后补0，可以理解为next[i] = 从0开始编号的next[i] + 1，也可理解为1..i-1的最长共同前后缀长度+1，因为比较的是前缀的前缀的下一个字符所以+1
传统next数组
0-base版本
struct kmp { /* 0-base时 j代表模式串已经匹配的子串的实尾指针，但不是已经匹配的长度 str, patt, pm均从0开始编号，意义不变 */ char *str; char *patt; int sl; int pl;
int pm[N];
void getPM () { pm[0] = 0; for (int i = 1, j = -1; i < pl; ++i) { while ((j + 1) && patt[j + 1] != patt[i]) j = pm[j] - 1; if (patt[j + 1] == patt[i]) ++j; pm[i] = j + 1; } /* 或者 pm[0] = 0; for (int i = 1, j = 0; i < pl; ++i) { while (j && patt[j] != patt[i]) j = pm[j - 1]; if (patt[j] == patt[i]) ++j; pm[i] = j; } //j为已经匹配的长度=审查指针，由于pm[i]是0..i的最长公共前后缀长度，故pm[j]在j失配时刚好是需要匹配的下一个字符指针 */ }
int search () { for (int i = 0, j = -1; i < sl; ++i) { while ((j + 1) && patt[j + 1] != str[i]) j = pm[j] - 1; if (patt[j + 1] == str[i]) ++j; if (j == pl - 1) { j = pm[j] - 1; return i - j; } }
return 0; }
kmp(char *str, char* patt, int sl, int pl) : str(str), patt(patt), sl(sl), pl(pl) {}}; vector<int> match(string &s, string &a) { memset(pma, 0, a.size() * sizeof(int)); vector<int> ai;
for (int i = 1, j = 0; i < a.size(); ++i) { while (j && a[j] != a[i]) j = pma[j - 1]; if (a[j] == a[i]) ++j; pma[i] = j; }
for (int i = 0, j = 0; i < s.size(); ++i) { while (j && a[j] != s[i]) j = pma[j - 1]; if (a[j] == s[i]) ++j; if (j == a.size()) ai.emplace_back(i - j + 1); }
return ai; }1-base版本
struct kmp { /* 1-base时 j代表模式串已经匹配的子串的实尾指针，同时是已经匹配的长度 str, patt, pm均从1开始编号，意义不变 */ char* str; char* patt; int sl; int pl; int pm[N];
void getPM() { // pm[0] = -1; pm[1] = 0; for (int i = 1, j = 0; i <= pl; ++i) { while (j && patt[j + 1] != patt[i]) j = pm[j]; if (patt[j + 1] == patt[i]) ++j; pm[i] = j; } }
int search() { for (int i = 1, j = 0; i <= sl; ++i) { while (j && patt[j + 1] != str[i]) j = pm[j]; if (patt[j + 1] == str[i]) ++j; if (j == pl) return i - j + 1; } }}next-val数组
//TODO
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！