KMP的理解

扩展KMP

Manacher的理解

HDU 3746 题目链接

题意

现在给你一个字符串， 问你需要再加多少个字符串才可以补齐一个循环（至少两个循环节）

思路

KMP算法中，求解nex数组就是根据自身与自身匹配进行求解最大公共前后缀 先求出整个数组的的最大公共前后缀，len - nex[len]就是最小循环节的长度（可以想一想）

#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; const int M = 1e4 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; typedef long long ll; char str[N]; int len; int nex[N]; int getNex() { int i = 0,j = -1; nex[0] = -1; while(i < len){ if (j == -1 || str[i] == str[j]){ i++; j++; nex[i] = j; } else { j = nex[j]; } } return len - nex[len]; } int main() { int t; scanf("%d",&t); while(t--){ scanf("%s",str); len = strlen(str); int loop_len = getNex(); if (loop_len != len && len % loop_len == 0){ printf("0\n"); } else printf("%d\n",loop_len - len % loop_len); } return 0; }

HDU 3336 题目链接

题意

给定一个字符串s，求s的每个前缀在此字符串中出现的次数，然后对次数求和，然后再对10007取模，就是要输出的答案。

思路1（dp+kmp）

假设长度为 len 的子串最大公共前后缀为 nex[len] 那么 i所得的贡献为 $$dp[len]=dp[nex[len]]+1；$$ $$因为长度为len-nex[len]的子串贡献已经求过了$$ $$那么新增加的贡献那就只有nex[len]这段加上他本身$$

#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; const int M = 1e4 + 5; const int INF = 0x3f3f3f3f; const int mod = 10007; typedef long long ll; char str[N]; int n; int nex[N]; int dp[N]; void getNex() { int i = 0,j = -1; nex[0] = -1; while(i < n){ if (j == -1 || str[i] == str[j]){ i++; j++; nex[i] = j; } else { j = nex[j]; } } } int main() { int t; scanf("%d",&t); while(t--){ scanf("%d",&n); scanf("%s",str); int ans = 0; dp[0] = 0; getNex(); for (int i = 1; i <= n; i++){ dp[i] = (dp[nex[i]] + 1) % mod; ans += dp[i]; ans %= mod; } cout << ans << endl; } return 0; }

思路2（扩展kmp）

在扩展kmp中，nex数组就是他的每个后缀与他本身的最大公共前缀 nex[i]就代表有nex[i]个前缀

#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; const int M = 1e6 + 5; const int INF = 0x3f3f3f3f; const int mod = 10007; typedef long long ll; char T[N],S[N]; int n,m; int nex[N]; int extend[N]; void getNex() { int a = 0,p = 0; nex[0] = m; for (int i = 1; i < m; i++){ if (i >= p || i + nex[i - a] >= p){ if (i >= p){ p = i; } while (p < m && T[p] == T[p - i]){ p++; } nex[i] = p - i; a = i; } else { nex[i] = nex[i - a]; } } } int main() { int t; scanf("%d",&t); while(t--){ scanf("%d",&m); scanf("%s",T); int ans = 0; getNex(); for (int i = 0; i < m; i++){ ans += nex[i]; ans %= mod; } cout << ans << endl; } return 0; }

HDU 3613

题意

给出26个字母的权值，第二行给出一行字符串，求其切成两半总价值最大为多少，如果分割子串不是回文串则价值为0

思路

利用Manacher算法计算整个字符串的回文长度，然后求出前缀、后缀是回文串的位置即可（利用生成的’#'区分前缀后缀）

#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; const int M = 1e4 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; typedef long long ll; char str[N]; char s[N]; int Len[N],len,index; bool pre[N],suf[N]; int value[33],sum[N]; int getstr() { int k = 0; str[k++] = '@';//开头加个特殊字符防止越界 for (int i = 0; i < index; i++) { str[k++] = '#'; str[k++] = s[i]; } str[k++] = '#'; str[k] = '\0'; // 防止越界 return k; // 新字符串的长度 } void Manacher() { int mx = 0,id = 0; len = getstr(); for (int i = 1; i < len; i++){ if (mx > i) { Len[i] = min(mx - i,Len[2 * id - i]); } else Len[i] = 1; while(str[i + Len[i]] == str[i - Len[i]]) Len[i]++; if (Len[i] + i > mx){ mx = Len[i] + i; id = i; } } } int main() { int t; scanf("%d",&t); while(t--){ for (int i = 0; i < 26; i++){ scanf("%d",&value[i]); } scanf("%s",s); index = strlen(s); memset(pre,false,sizeof(pre)); memset(suf,false,sizeof(suf)); memset(sum,0,sizeof(sum)); for (int i = 1; i <= index; i++){ sum[i] = sum[i - 1] + value[s[i - 1] - 'a']; } Manacher(); for (int i = 1; i < len; i++){ if (Len[i] - 1 == index) continue; /// 长度是整个字符串，不行 if (i - Len[i] == 0) pre[i + Len[i] - 1] = true; if (i + Len[i] == len) suf[i - Len[i] + 1] = true; // cout << "str=" << str[i] << " Len[i]=" << Len[i] << " i = " << i << " index =" << index << endl; } int ans = 0; for (int i = 3; i < len - 1; i++){ if (i % 2 == 0) continue; int cur = 0; // cout << "i = " << i << " pre = " << pre[i] << " suf=" << suf[i]; // cout << " sum[index]=" << sum[index] << " sum[i]=" << sum[i / 2] << endl; if (pre[i]) cur += sum[i / 2]; if (suf[i]) cur += (sum[index] - sum[i / 2]); ans = max(ans,cur); } cout << ans << endl; } return 0; }

POJ 3376 题目链接 扩展KMP + Trie

题意

有n个字符串,两两配对，有n * n种组合方式，问你有多少种方式能形成回文串

思路

由两个字符串a,b.要使它们能组成回文串有三种情况 1.alen < blen 时 a是b的反串前缀，且b的剩余部分是后缀回文串 2.alen > blen b的反串是a的前缀，且a的后缀是回文串 3.alen == blen b的反串等于a 所以我们可以根据一个字符串的反串与其他字符串进行匹配，如果满足上述三种情况的一种，那就能组成回文串 我们使用字典树进行匹配，将所有的反串都放到字典树中，然后使用所有正串与之匹配 还有一个问题就是如何判断后缀回文串（可以使用Manacher也可以使用正反串匹配扩展KMP） 在这里正反串都出现了，所以使用扩展KMP就行了（只要满足extend[i] + i == len即为后缀回文串） 学会了一种新的输入方式：因为只给了字符串的总长度，所以，只开一维的字符串数组，每次接着上次字符串结束的位置开始即可。为了方便，用一个数组保存每个串的起始位置

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std; const int N = 2e6 + 5; const int M = 1e4 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; typedef long long ll; char str[N],rev[N]; int Len[N],len; int nex[N],extend[N]; int tree[N][26]; int num[N],pla[N]; int pos = 1; /// 初始值为1 void Insert(char word[],int n) { int p = 0; for (int i = 0; i < n; i++){ int x = word[i] - 'a'; if (tree[p][x] == 0){ tree[p][x] = pos++; } if (extend[i] + i == n){ /// 后缀是回文串 pla[p]++; } p = tree[p][x]; } num[p]++; /// 在这里结束的个数 } int Find(char word[],int n) { int p = 0; int ans = 0; bool flag = true; for (int i = 0; i < n; i++){ int x = word[i] - 'a'; if (tree[p][x] == 0) { flag = false; break; } if (extend[i] + i == n){ /// 这里能够形成回文串后缀，加上在这里结束的数量 ans += num[p]; } p = tree[p][x]; } if (flag) ans += num[p] + pla[p]; /// 加上在这里结束的数量和此时后缀有回文串的数量 return ans; } void getNex(char T[],int m) { int a = 0,p = 0; nex[0] = m; for (int i = 1; i < m; i++){ if (i >= p || i + nex[i - a] >= p){ if (i >= p){ p = i; } while (p < m && T[p] == T[p - i]){ p++; } nex[i] = p - i; a = i; } else { nex[i] = nex[i - a]; } } } void getExtend(char S[],char T[],int n,int m) { int a = 0,p = 0; for (int i = 0; i < n; i++){ if (i >= p || i + nex[i - a] >= p){ if (i >= p){ p = i; } while (p < n && p - i < m && S[p] == T[p - i]){ p++; } extend[i] = p - i; a = i; } else { extend[i] = nex[i - a]; } } } int main() { int n; scanf("%d",&n); for (int i = 0; i < n; i++){ scanf("%d %s",&len,str + Len[i]); Len[i + 1] = Len[i] + len; char *S = str + Len[i]; memcpy(rev,S,len); // cout << "rev = " << rev << endl; reverse(rev,rev + len); // cout << "reverse(rev) = " << rev << endl; getNex(S,len); /// 这时候加入到字典树的是反串，所以要用正串匹配反串求出反串的后缀回文串 getExtend(rev,S,len,len); Insert(rev,len); } ll ans = 0; for (int i = 0; i < n; i++){ char *S = str + Len[i]; int len = Len[i + 1] - Len[i]; memcpy(rev,S,len); reverse(rev,rev + len); getNex(rev,len); getExtend(S,rev,len,len); ans += Find(S,len); } cout << ans << endl; return 0; }

HDU 4513 题目链接

题意

吉哥又想出了一个新的完美队形游戏！ 　　假设有n个人按顺序站在他的面前，他们的身高分别是h[1], h[2] … h[n]，吉哥希望从中挑出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则就是新的完美队形： 　　1、挑出的人保持原队形的相对顺序不变，且必须都是在原队形中连续的； 　　2、左右对称，假设有m个人形成新的队形，则第1个人和第m个人身高相同，第2个人和第m-1个人身高相同，依此类推，当然如果m是奇数，中间那个人可以任意； 　　3、从左到中间那个人，身高需保证不下降，如果用H表示新队形的高度，则H[1] <= H[2] <= H[3] … <= H[mid]。 　　现在吉哥想知道：最多能选出多少人组成新的完美队形呢？

思路

在Manacher的基础上判断一下两边的数是否大于中间

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std; const int N = 2e6 + 5; const int M = 1e4 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; typedef long long ll; int str[N]; int s[N]; int Len[N]; int n; int getstr() { int k = 0; str[k++] = -1;//开头加个特殊字符防止越界 for (int i = 0; i < n; i++) { str[k++] = -2; str[k++] = s[i]; } str[k++] = -2; str[k] = 0; // 防止越界 return k; // 新字符串的长度 } int Manacher() { int ans = 0; int mx = 0,id = 0; int len = getstr(); for (int i = 1; i < len; i++){ if (mx > i) { Len[i] = min(mx - i,Len[2 * id - i]); } else Len[i] = 1; while(str[i + Len[i]] == str[i - Len[i]]) { if (str[i + Len[i]] != -2 && str[i + Len[i] - 2] < str[i + Len[i]]) break; Len[i]++; } if (Len[i] + i > mx){ mx = Len[i] + i; id = i; ans = max(ans,Len[i]); } } return ans - 1; } int main() { int t; scanf("%d",&t); while(t--){ scanf("%d",&n); for (int i = 0; i < n; i++){ scanf("%d",&s[i]); } printf("%d\n",Manacher()); } return 0; }