[kuangbin带你飞]专题十六 KMP 扩展KMP Manacher

2023-10-26 08:30:41

A
KMP模版

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 1000000 + 5;
const int maxm = 10000 + 5;void getFail(int* p, int m, int* f) {f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
int find(int* t, int n, int* p, int m, int* f) {getFail(p, m, f);int j = 0;for(int i = 0; i < n; ++i) {while(j && p[j] != t[i]) j = f[j];if(p[j] == t[i]) j++;if(j == m) return i - m + 1;}return -1;
}
int a[maxn], b[maxm];
int f[maxn];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while(t--) {int n, m;cin >> n >> m;for(int i = 0; i < n; ++i) cin >> a[i];for(int i = 0; i < m; ++i) cin >> b[i];int ans = find(a, n, b, m, f);cout << (ans == -1 ? -1 : ans + 1) << endl;}
}

B
kmp魔改题，kmp匹配成功后变为失配的位置，即最长公共前后缀

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const int maxm = 1e4 + 5;
void getFail(char* p, int* f) {int m = strlen(p);f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
int find(char* t, char* p, int* f) {int n = strlen(t), m = strlen(p);getFail(p, f);int j = 0;int ans = 0;for(int i = 0; i < n; ++i) {while(j && p[j] != t[i]) j = f[j];if(p[j] == t[i]) j++;if(j == m) {ans++;j = f[j];}}return ans;
}
char P[maxm], T[maxn];
int f[maxm];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while(t--) {cin >> P >> T;cout << find(T, P, f) << endl;}
}

C

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const int maxm = 1e4 + 5;
void getFail(char* p, int* f) {int m = strlen(p);f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
int find(char* t, char* p, int* f) {int n = strlen(t), m = strlen(p);getFail(p, f);int j = 0;int ans = 0;for(int i = 0; i < n; ++i) {while(j && p[j] != t[i]) j = f[j];if(p[j] == t[i]) j++;if(j == m) {ans++;j = 0;}}return ans;
}
char P[maxm], T[maxn];
int f[maxm];
int main()
{ios::sync_with_stdio(false);cin.tie(0);while(cin >> T) {if(strlen(T) == 1 && T[0] == '#') break;cin >> P;cout << find(T, P, f) << endl;}
}

D
补全循环节
f[n] && n * (n - f[n]) == 0表示存在n ／ (n - f[n])个循环节
若不存在，则n-f[n]为存在的最小循环节长度，我们即需要补全n - f[n] - n % (n - f[n])

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
void getFail(char* p, int* f) {int m = strlen(p);f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
char P[maxn];
int f[maxn];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while(t--) {cin >> P;getFail(P, f);int n = strlen(P);if(f[n] == 0) cout << n << endl;else if(n % (n - f[n]) == 0) cout << 0 << endl;else cout << (n - f[n] - n % (n - f[n])) << endl;}
}

E
循环节

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
void getFail(char* p, int* f) {int m = strlen(p);f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
char P[maxn];
int f[maxn];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n, cas = 1;while(cin >> n) {if(n == 0) break;cin >> P;getFail(P, f);cout << "Test case #" << cas++ << endl;for(int i = 0; i <= n; ++i) {if(f[i] && i % (i - f[i]) == 0) {cout << i << " " << i / (i - f[i]) << endl;}}cout << endl;}
}

G

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
void getFail(char* p, int* f) {int m = strlen(p);f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
char P[maxn];
int f[maxn];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n, cas = 1;while(cin >> P) {if(strlen(P) == 1 && P[0] == '.') break;getFail(P, f);int n = strlen(P);if(f[n] && n % (n - f[n]) == 0) cout << n / (n - f[n]) << endl;else cout << 1 << endl;}
}

H
next数组的意义

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
void getFail(char* p, int* f) {int m = strlen(p);f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
char P[maxn];
int f[maxn];
int ans[maxn], tot;
int main()
{ios::sync_with_stdio(false);cin.tie(0);while(cin >> P) {getFail(P, f);int n = strlen(P);tot = 0;ans[tot++] = n;while(f[n]) {ans[tot++] = f[n];n = f[n];}for(int i = tot - 1; i >= 0; --i) {if(i == tot - 1) cout << ans[i];else cout << " " << ans[i];}cout << endl;}
}

I
暴力枚举最长公共子串，用kmp判断即可

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 60 + 5;
void getFail(char* p, int m, int* f) {f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
bool find(char* t, char* p, int m, int* f) {int n = strlen(t);getFail(p, m, f);int j = 0;int ans = 0;for(int i = 0; i < n; ++i) {while(j && p[j] != t[i]) j = f[j];if(p[j] == t[i]) j++;if(j == m) return true;}return false;
}
char T[15][maxn];
char ch[4] = {'A', 'C', 'G', 'T'};
char P[maxn];
int f[maxn];
int ans = 0, n;
char ans_ch[maxn];
void dfs(int m) {for(int i = 0; i < 4; ++i) {P[m] = ch[i];bool flg = true;for(int j = 0; j < n; ++j) {if(!find(T[j], P, m + 1, f)) {flg = false;break;}}if(flg) {if(ans < m + 1) {for(int j = 0; j < m + 1; ++j) ans_ch[j] = P[j];ans = m + 1;}dfs(m + 1);}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while(t--) {ans = 0;cin >> n;for(int i = 0; i < n; ++i) cin >> T[i];dfs(0);if(ans < 3) cout << "no significant commonalities" << endl;else {for(int i = 0; i < ans; ++i) cout << ans_ch[i];cout << endl;}}
}

J
拼接两个字符串，将两个字符串中间加入特殊字符.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
void getFail(char* p, int* f) {int m = strlen(p);f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
char P[maxn], T[maxn];
int f[maxn];
int main()
{ios::sync_with_stdio(false);cin.tie(0);while(cin >> P) {int n = strlen(P);cin >> T;int m = n + strlen(T) + 1;for(int i = n + 1; i < m; ++i) P[i] = T[i - n - 1];P[n] = '.';getFail(P, f);if(f[m] == 0) cout << 0 << endl;else {for(int i = 0; i < f[m]; ++i) cout << P[i];cout << " " << f[m] << endl;}}
}

K
next数组计算的是子串中最长公共前后缀的长度
我们令cnt[i]表示以第i个字符结尾的所有前缀出现的次数，则cnt[i]=cnt[next[i]]+1

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 200000 + 5;
const int maxm = 200000 + 5;
const int mod = 10007;
void getFail(char* p, int* f) {int m = strlen(p);f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
int find(char* t, char* p, int* f) {int n = strlen(t), m = strlen(p);getFail(p, f);int j = 0;int ans = 0;for(int i = 0; i < n; ++i) {while(j && p[j] != t[i]) j = f[j];if(p[j] == t[i]) j++;if(j == m) {ans++;j = f[j];}}return ans % mod;
}
char P[maxm], T[maxn];
int f[maxm], cnt[maxn];
int main()
{int t;scanf("%d", &t);while(t--) {int n;scanf("%d", &n);scanf("%s", T);getFail(T, f);int ans = 0;memset(cnt, 0, sizeof(cnt));for(int i = 1; i <= n; ++i) {cnt[i] = cnt[f[i]] + 1;ans = (ans + cnt[i]) % mod;}printf("%d\n", ans);}
}

L
原本为密文 + 明文，我们通过给出转换为-》明文 + 未知
即使用exkmp找最长前后缀

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;void GetNext(char *str, int* Next)
{int i=0,j,pos,len=strlen(str);Next[0]=len;   //初始化next[0]while(i+1pos+next[pos],则从头开始while(i+j> t;while(t--) {cin >> a;for(int i = 0; a[i] != '\0'; ++i) match[a[i]] = i + 'a';cin >> T;for(int i = 0; T[i] != '\0'; ++i) P[i] = match[T[i]];int n = strlen(T);int maxx = n;ExKMP(T, P, f, ex);for(int i = 0; i < n; ++i) {if(i + ex[i] >= n && i >= ex[i]) {maxx = i;break;}}for(int i = 0; i < maxx; ++i) cout << T[i];for(int i = 0; i < maxx; ++i) cout << match[T[i]];cout << endl;}
}

M
暴力枚举子串，KMP匹配即可

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 100 + 5;
void getFail(char* p, int m, int* f) {f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
bool find(char* t, char* p, int m, int* f) {int n = strlen(t);getFail(p, m, f);int j = 0;int ans = 0;for(int i = 0; i < n; ++i) {while(j && p[j] != t[i]) j = f[j];if(p[j] == t[i]) j++;if(j == m) return true;}return false;
}
char P1[maxn], P2[maxn], T[maxn][maxn];
int f1[maxn], f2[maxn];int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while(t--) {int n;cin >> n;for(int i = 0; i < n; ++i) cin >> T[i];int m = strlen(T[0]), tot;int ans = 0;for(int i = 0; i < m; ++i) {for(int j = i + ans; j < m; ++j) {tot = 0;for(int k = i; k <= j; ++k) P1[tot++] = T[0][k];for(int k = 0; k < tot; ++k) P2[k] = P1[tot - 1 - k];bool flg = true;getFail(P1, tot, f1);getFail(P2, tot, f2);for(int k = 1; k < n; ++k) {if(!find(T[k], P1, tot, f1) && !find(T[k], P2, tot, f2)) {flg = false;break;}}if(flg) ans = j - i + 1;}}cout << ans << endl;}
}

N
暴力KMP匹配

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 200 + 5;
void getFail(char* p, int m, int* f) {f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
bool find(char* t, char* p, int m, int* f) {int n = strlen(t);getFail(p, m, f);int j = 0;int ans = 0;for(int i = 0; i < n; ++i) {while(j && p[j] != t[i]) j = f[j];if(p[j] == t[i]) j++;if(j == m) return true;}return false;
}
char P[maxn], T[4005][maxn];
int f[maxn];
char sub[maxn];int main()
{ios::sync_with_stdio(false);cin.tie(0);int n;while(cin >> n) {if(n == 0) break;for(int i = 0; i < n; ++i) cin >> T[i];int m = strlen(T[0]), tot;int ans = 0;for(int i = 0; i < m; ++i) {for(int j = i + (ans == 0 ? 0 : ans - 1); j < m; ++j) {tot = 0;for(int k = i; k <= j; ++k) P[tot++] = T[0][k];bool flg = true;getFail(P, tot, f);for(int k = 1; k < n; ++k) {if(!find(T[k], P, tot, f)) {flg = false;break;}}if(flg && ans < j - i + 1) {ans = j - i + 1;for(int k = 0; k < ans; ++k) {sub[k] = T[0][i + k];}} else if(flg && ans == j - i + 1) {bool ex = false;for(int k = 0; k < ans; ++k) {if(T[0][i + k] < sub[k]) {ex = true;break;}else if(T[0][i + k] > sub[k]) {ex = false;break;}}if(ex) for(int k = 0; k < ans; ++k) sub[k] = T[0][i + k];}}}if(ans == 0) cout << "IDENTITY LOST" << endl;else {for(int i = 0; i < ans; ++i) cout << sub[i];cout << endl;}}
}

O
能出现多少次，就要看循环节有多少个了
再就是求最大最小表示

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1000000 + 5;void getFail(char *p, int *f) {int m = strlen(p);f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
int get_minstring(char *s) {int len = strlen(s);int i = 0, j = 1, k = 0;while(i < len && j < len && k < len) {int t = s[(i + k) % len] - s[(j + k) % len];if(t == 0) k++;else {if(t > 0) i = i + k + 1;else j = j + k + 1;if(i == j) j++;k = 0;}}return min(i, j);
}
int get_maxstring(char *s) {int len = strlen(s);int i = 0, j = 1, k = 0;while(i < len && j < len && k < len) {int t = s[(i + k) % len] - s[(j + k) % len];if(t == 0) k++;else {if(t > 0) j = j + k + 1;else i = i + k + 1;if(i == j) j++;k = 0;}}return min(i, j);
}
int f[maxn];
char str[maxn];
int main()
{ios::sync_with_stdio(false);cin.tie(0);while(cin >> str) {getFail(str, f);int len = strlen(str);int cnt = len / (len - f[len]);cout << get_minstring(str) + 1 << " " << cnt << " " << get_maxstring(str) + 1 << " " << cnt << endl;}
}

P
转换为最小表示，用set维护

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int get_minstring(string s) {int len = s.length();int i = 0, j = 1, k = 0;while(i < len && j < len && k < len) {int t = s[(i + k) % len] - s[(j + k) % len];if(t == 0) k++;else {if(t > 0) i = i + k + 1;else j = j + k + 1;if(i == j) j++;k = 0;}}return min(i, j);
}
set mp;
string str;
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n;while(cin >> n) {mp.clear();for(int i = 0; i < n; ++i) {cin >> str;int len = str.length();int pos = get_minstring(str);string tmp = "";for(int i = 0; i < len; ++i) {tmp += str[(i + pos) % len];}if(mp.find(tmp) == mp.end()) mp.insert(tmp);}cout << mp.size() << endl;}
}

Q
exkmp

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1000000 + 5;
void pre_EKMP(char x[], int m, int next[]){next[0] = m;int j = 0;while( j+1 < m && x[j] == x[j+1] )j++; next[1] = j;int k = 1;for(int i = 2; i < m; i++){int p = next[k] + k - 1;int L = next[i - k];if(i + L < p + 1) next[i] = L;else {j = max(0, p - i + 1);while( i+j < m && x[i+j] == x[j])j++; next[i] = j;k = i;}}
}
void EKMP(char x[], int m, char y[], int n, int next[], int extend[]) { //计算y的后缀与x的最长前缀pre_EKMP(x, m, next);int j = 0;while(j < n && j < m && x[j] == y[j]) j++; extend[0] = j;int k = 0;for(int i = 1;i < n;i++){int p = extend[k]+k-1;int L = next[i-k];if(i+L < p+1)extend[i] = L;else {j = max(0,p - i + 1);while( i+j < n && j < m && y[i+j] == x[j] )j++; extend[i] = j;k = i;}}
}
char str[maxn];
int f[maxn], ex[maxn];
vector ans;
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;for(int cas = 1; cas <= t; ++cas) {cin >> str;int n = strlen(str);EKMP(str, n, str, n, f, ex);ans.clear();for(int i = 1; i < n; ++i) {if(ex[i] + i == n) ans.push_back(i);}cout << "Case #" << cas << ": " << ans.size() + 1 << endl;for(int i = 0; i < ans.size(); ++i) cout << ans[i] << " ";cout << n << endl;}
}

S
exkmp去求是否为回文串，若i位置时i+ex[i]=n表示后面的串形成回文串

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 500000 + 5;
void pre_EKMP(char x[], int m, int next[]){next[0] = m;int j = 0;while( j+1 < m && x[j] == x[j+1] )j++; next[1] = j;int k = 1;for(int i = 2; i < m; i++){int p = next[k] + k - 1;int L = next[i - k];if(i + L < p + 1) next[i] = L;else {j = max(0, p - i + 1);while( i+j < m && x[i+j] == x[j])j++; next[i] = j;k = i;}}
}
void EKMP(char x[], int m, char y[], int n, int next[], int extend[]) { //计算y的后缀与x的最长前缀pre_EKMP(x, m, next);int j = 0;while(j < n && j < m && x[j] == y[j]) j++; extend[0] = j;int k = 0;for(int i = 1;i < n;i++){int p = extend[k]+k-1;int L = next[i-k];if(i+L < p+1)extend[i] = L;else {j = max(0,p - i + 1);while( i+j < n && j < m && y[i+j] == x[j] )j++; extend[i] = j;k = i;}}
}
int val[30];
char S[maxn], T[maxn];
int f[maxn], ex1[maxn], ex2[maxn];
int sum[maxn];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while(t--) {for(int i = 0; i < 26; ++i) cin >> val[i];cin >> S;int n = strlen(S);for(int i = 0; i < n; ++i) {T[n - 1 - i] = S[i];sum[i + 1] = sum[i] + val[S[i] - 'a'];}EKMP(T, n, S, n, f, ex1);EKMP(S, n, T, n, f, ex2);int ans = -0x3f3f3f3f;for(int i = 1; i < n; ++i) {int tmp = 0;if(i + ex1[i] == n) tmp += sum[n] - sum[i];if(n - i + ex2[n - i] == n) tmp += sum[i];//cout << "i = " << i << ", ex1 = " << ex1[i] << ", ex2 = " << ex2[n - i] << endl; ans = max(tmp, ans);}cout << ans << endl;}
}

T
分类讨论 + trie + exkmp

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 2000005;
const int KIND = 26;struct TrieNode
{int num;    // 到当前节点的字符串个数int cnt;    // 当前节点后面回文子串个数TrieNode* nxt[26];
};TrieNode node[MAXN];
TrieNode* root;           // trie树的根节点
int bg[MAXN];             // bg[i]第i+1个字符串开始的位置
int ed[MAXN];             // ed[i]第i+1个字符串结束的位置
bool flag[2][MAXN];       // flag[0][i]为true表示原串后面为回文串   flag[1][i]表示反串
char S[MAXN];             // 存放原串
char T[MAXN];             // 存放反串
int nxt[MAXN];            // 存放next数组
int extend[MAXN];         // 用于判断是否为回文子串
LL ans;                   // 保存结果
int tot;                  // node数组的下标void GetNext(char* T, int lhs, int rhs)
{int j = 0;while (lhs + j + 1 <= rhs && T[lhs + j] == T[lhs + j + 1]) ++j;nxt[lhs + 1] = j;int k = lhs + 1;for (int i = lhs + 2; i <= rhs; ++i){int p = nxt[k] + k - 1;int L = nxt[lhs + i - k];if (L + i < p + 1) nxt[i] = L;else{j = max(0, p - i + 1);while (i + j <= rhs && T[lhs + j] == T[i + j]) ++j;nxt[i] = j;k = i;}}
}void ExtendKMP(char* S, char* T, int lhs, int rhs, bool sign)
{GetNext(T, lhs, rhs);int j = 0;while (j + lhs <= rhs && S[j + lhs] == T[j + lhs]) ++j;extend[lhs] = j;int k = lhs;for (int i = lhs + 1; i <= rhs; ++i){int p = extend[k] + k - 1;int L = nxt[lhs + i - k];if (L + i < p + 1) extend[i] = L;else{j = max(0, p - i + 1);while (i + j <= rhs && S[i + j] == T[lhs + j]) ++j;extend[i] = j;k = i;}}for (int i = lhs; i <= rhs; ++i){if (extend[i] == rhs - i + 1)flag[sign][i] = true;}
}void Insert(char S[], int lhs, int rhs)
{TrieNode* temp = root;for (int i = lhs; i <= rhs; ++i){int ch = S[i] - 'a';temp->cnt += flag[0][i];    // 更新当前节点后面回文子串的数目if (temp->nxt[ch] == NULL) temp->nxt[ch] = &node[tot++];temp = temp->nxt[ch];}++temp->num; // 更新到当前节点的字符串数目
}void Search(char S[], int lhs, int rhs)
{TrieNode* temp = root;for (int i = lhs; i <= rhs; ++i){int ch = S[i] - 'a';temp = temp->nxt[ch];if (temp == NULL) break;if ((i < rhs && flag[1][i + 1]) || i == rhs)ans += temp->num;}if (temp) ans += temp->cnt;
}int main()
{int n;while (scanf("%d", &n) != EOF){// 初始化tot = 0;ans = 0;memset(node, 0, sizeof(node));memset(flag, 0, sizeof(flag));root = &node[tot++];int l = 0;int L = 0;for (int i = 0; i < n; ++i){// 输入一组数据scanf("%d", &l);scanf("%s", S + L);// 生成反串for (int j = 0; j < l; ++j)T[L + j] = S[L + l - 1 - j];bg[i] = L;ed[i] = L + l - 1;ExtendKMP(S, T , bg[i], ed[i], 0);ExtendKMP(T, S , bg[i], ed[i], 1);Insert(S, bg[i], ed[i]);L += l;}for (int i = 0; i < n; ++i)Search(T, bg[i], ed[i]);printf("%lld\n", ans);}return 0;
}

U
Manacher算法板子

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1000000 + 5;char str[maxn], s[maxn << 1];
int pal[maxn << 1], len;
void build() {s[0] = '@';s[1] = '#';len = strlen(str);for(int i = 0; i < len; ++i) {s[2 * i + 2] = str[i];s[2 * i + 3] = '#';}s[2 * len + 2] = '\0';
}
void manacher() {build();int mx = 0, id;len = 2 * len + 2;for(int i = 0; i < len; ++i) {if(mx > i) pal[i] = min(pal[2 * id - i], mx - i);else pal[i] = 1;for(; s[i - pal[i]] == s[i + pal[i]]; pal[i]++)if(pal[i] + i > mx) {mx = pal[i] + i;id = i;}}
}int main()
{int cas = 1;while(~scanf("%s", &str)) {if(str[0] == 'E') break;manacher();int ans = 0;for(int i = 0; i < len; ++i) {ans = max(ans, pal[i]);}printf("Case %d: %d\n", cas++, ans - 1);}
}

V
Manacher魔改题
对pal数组更新时加入递减判断条件

#include 
using namespace std;
const int maxn = 100000 + 5;int f[maxn], fx[maxn << 1];
int pal[maxn << 1], n, m;
void build() {fx[0] = -1;fx[1] = 300;for(int i = 0; i < n; ++i) {fx[2 * i + 2] = f[i];fx[2 * i + 3] = 300;}
}
int manacher() {build();int mx = 0, id, ans = 0, k;m = 2 * n + 2;for(int i = 0; i < m; ++i) {if(mx > i) pal[i] = min(pal[2 * id - i], mx - i);else pal[i] = 1;k = fx[i];while(fx[i - pal[i]] == fx[i + pal[i]] && ((fx[i - pal[i]] == 300) || (fx[i - pal[i]] <= k))) {if(fx[i - pal[i]] != 300) k = fx[i - pal[i]];pal[i]++;}if(pal[i] + i > mx) {mx = pal[i] + i;id = i;}ans = max(ans, pal[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", &f[i]);if(n == 1) {printf("1\n");continue;}printf("%d\n", manacher());}
}

W
manacher

#include 
using namespace std;
const int maxn = 200000 + 5;
char str[maxn], s[maxn << 1];
int pal[maxn << 1], mapp[30], n;
void build() {s[0] = '@';s[1] = '#';for(int i = 0; i < n; ++i) {s[2 * i + 2] = str[i];s[2 * i + 3] = '#';}s[2 * n + 2] = '\0';
}
void manacher() {build();int mx = 0, id;n = 2 * n + 2;for(int i = 0; i < n; ++i) {if(mx > i) pal[i] = min(pal[2 * id - i], mx - i);else pal[i] = 1;for(; s[i - pal[i]] == s[i + pal[i]]; pal[i]++)if(pal[i] + i > mx) {mx = pal[i] + i;id = i;}}
}int main()
{char tar[5];while(~scanf("%s", &tar)) {scanf("%s", &str);int now = 0, noww = 0;for(int i = tar[0] - 'a'; i + 'a' <= 'z'; ++i) {mapp[i] = now;now++;}while(now + 'a' <= 'z') {mapp[noww++] = now++;}n = strlen(str);for(int i = 0; i < n; ++i) str[i] = mapp[str[i] - 'a'] + 'a';manacher();int pos = -1, len = 0;for(int i = 0; i < n; ++i) {if(pal[i] - 1 > len) {len = pal[i] - 1;pos = i;}}if(len < 2) {puts("No solution!");continue;}int l = s[pos] == '#' ? ((pos - 3) / 2 - len / 2 + 1) : ((pos - 2) / 2 - len / 2);int r = l + len - 1;printf("%d %d\n", l, r);for(int i = l; i <= r; ++i) putchar(str[i]);puts("");}
}

Z
求给的字符串中的字串需要满足为前后缀且当中还需要出现的最长长度

#include 
using namespace std;
const int maxn = 1e6 + 5;
void getFail(char* p, int m, int* f) {f[0] = 0, f[1] = 0;for(int i = 1; i < m; ++i) {int j = f[i];while(j && p[i] != p[j]) j = f[j];f[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
int find(char* t, int l, int r, char* p, int m, int* f) {getFail(p, m, f);int j = 0;for(int i = l; i < r; ++i) {while(j && p[j] != t[i]) j = f[j];if(p[j] == t[i]) j++;if(j == m) return i - m + 1;}return -1;
}
char str[maxn];
int f[maxn];
int main()
{int t;scanf("%d", &t);while(t--) {scanf("%s", &str);int n = strlen(str);getFail(str, n, f);int k = f[n], ans = 0;while(k) {if(k * 2 >= n) {k = f[k];continue;}if(find(str, k, n - k, str, k, f) != -1) {ans = k;break;}k = f[k];}printf("%d\n", ans);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！

标签：技术

上一篇 > （学习笔记-TCP连接断开）TCP四次挥手
下一篇 > 【Spring】手动回滚事务，编程式事务的应用场景理解

Duilib中list控件支持ctrl和shif多行选中的实现

[ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif

win10系统微软输入法于eclipse ctrl+shif+f冲突间接处理办法

Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif

读LDD3，内存映射与DMA--PAGE_SHIF…

VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】

更换iBus五笔的左与右Shif

sublime ctrl+shif+f 没用解决办法

idea 对 ctrl + z 的撤销是 ctrl + shif + z

计算机最早的设计师应用于,计算机应用基础选择题doc.doc

win10自带截图神器：Win+Shift+S

Python基础之文件目录操作

python简述目录_Python基础之文件目录操作(示例代码)

tp5 如何做数据采集

任务2-7(服务器字体+阿里巴巴矢量库)

html标签（1)：h1~h6,p,br,pre,hr

TI 电量计介绍与芯片选型指南

几款TI电源芯片简介

TI DSP芯片C2000系列读取FLASH数据

德州仪器(Ti)平台嵌入式开发基础

TI三相电机智能栅极驱动芯片特点分类

省选模拟（12.08） T3 圈圈圈圈圈圈圈圈

Hadoop生态圈技术栈（上）

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询

小猿圈之Linux下Mysql 操作命令

大数据Hadoop生态圈常用面试题

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作

备战Noip2018模拟赛11（B组）T3 Monogatari 物语

【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码

NYOJ 78 圈水池

递归问题跑道汽车绕圈问题 Python实现

Hadoop生态圈（三）：MapReduce

[kuangbin带你飞]专题十六 KMP 扩展KMP Manacher

相关文章