字符串哈希+KMP

P10468 兔子与兔子

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 1000010;
ull a[N], pw[N];
int n;
ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l + 1];
}
signed main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);string s; cin >> s;s = " " + s; int base = 131;pw[0] = 1;for(int i = 1; i <= s.size(); i++){a[i] = a[i - 1] * base + (ull)s[i];pw[i] = pw[i - 1] * base;}cin >> n;for(int i = 1; i <= n; i++){int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;ull x = gethash(l1, r1), y = gethash(l2, r2);if(x == y)cout << "Yes" << endl;else cout << "No" << endl;} return 0;
}

P3375 【模板】KMP

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int nex[1000005];
void getnext(char s[], int ls){int j = 0;nex[0] = 0;for(int i = 1; i < ls; i++){while(j > 0 && s[i] != s[j])j = nex[j - 1];if(s[i] == s[j]){j++;}nex[i] = j;}
}
signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);char p[1000005], s[1000005];cin >> p;cin >> s;int lp = strlen(p);int ls = strlen(s);getnext(s, ls);int i = 0;int j = 0;while(i < lp){if(p[i] == s[j]){i++, j++;}else{if(j > 0)j = nex[j - 1];else i++;}if(j == ls){cout << i - ls + 1 << endl;j = nex[j - 1];}}for(int i = 0; i < ls; i++)cout << nex[i] << " ";return 0;
}

P4391 [BalticOI 2009] Radio Transmission 无线传输

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int nex[1000005];
int n;
void getnext(int ls, char s[]){nex[0] = 0;int j = 0;for(int i = 1; i < ls; i++){while(j > 0 && s[i] != s[j])j = nex[j - 1];if(s[i] == s[j])j++;nex[i] = j;}
}
signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n;char s[1000005];for(int i = 0; i < n; i++)cin >> s[i];getnext(n, s);int ans = nex[n - 1];cout << n - ans << endl;return 0;
}

P1470 [USACO2.3] 最长前缀 Longest Prefix

深搜加记忆化

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
string s, s1;
map<char, vector<string> > mp;
int len, dp[200010];
int dfs(int pos){int ans = 0, b = 0;if(pos == len)return pos;if(dp[pos])return dp[pos];if(mp[s[pos]].empty())return pos;for(int i = 0; i < mp[s[pos]].size(); i++){string s2 = mp[s[pos]][i];int len2 = s2.size();string s3 = s.substr(pos, len2);if(s2 == s3){ans = max(ans, dfs(pos + len2));b = 1;}}if(b)return dp[pos] = ans;else return dp[pos] = pos;
}
signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);while(1){cin >> s;if(s == ".")break;mp[s[0]].push_back(s);}s = "";while(cin >> s1)s += s1;len = s.size();cout << dfs(0) << endl; return 0;
}

KMP  还没有调出来

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
string s, s1;
int nex[200010];
int km[205][200010];
int dp[200010];
void kmp(int pos, string st){memset(nex, 0, sizeof(nex));nex[0] = 0;int j = 0;for(int i = 1; i < st.size(); i++){while(j > 0 && st[i] != st[j])j = nex[j - 1];if(st[i] == st[j])j++;nex[i] = j;}j = 0;int i = 0;while(i < s.size()){if(s[i] == st[j])i++, j++;else{if(j > 0)j = nex[j - 1];else i++;}if(j == st.size()){km[pos][i] = 1;j = nex[j - 1];}}
}
signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);vector<string> v;while(1){cin >> s;if(s == ".")break;v.push_back(s);}cin >> s;for(int i = 0; i < v.size(); i++)kmp(i, v[i]);dp[0] = 1;for(int i = 1; i <= s.size(); i++){for(int j = 0; j < v.size(); j++){if(km[j][i] && i > v[j].size()){dp[i] = dp[i] || dp[i - v[j].size()];}}}for(int i = s.size(); i >= 0; i--){if(dp[i]){cout << i << endl;return 0;}}return 0;
}

CF25E Test

也是没调出来

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int nex[100010];
void getnext(string st){memset(nex, 0, sizeof(nex));nex[0] = 0;int j = 0;for(int i = 1; i < st.size(); i++){while(j > 0 && st[i] != st[j])j = nex[j - 1];if(st[i] == st[j])j++;nex[i] = j;}
}
signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);string s1, s2, s3; cin >> s1 >> s2 >> s3;getnext(s2);int flag1 = -1;int i = 0, j = 0;while(i < s1.size()){if(s1[i] == s2[j])i++, j++;else{if(j > 0)j = nex[j - 1];else i++;}if(i == s1.size()){flag1 = j;}}string s = s1;if(flag1 == -1)s += s2;else{for(int i = flag1; i < s2.size(); i++)s += s2[i];}int flag2 = -1;getnext(s);i = 0, j = 0;while(i < s.size()){if(s[i] == s3[j])i++, j++;else{if(j > 0)j = nex[j - 1];else i++;}if(i == s.size()){flag2 = j;}}if(flag2 == -1)s += s3;else{for(int i = flag2; i < s3.size(); i++)s += s3[i];}cout << s.size() << endl;return 0;
}