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;
}