第十一个数据RE 求助大佬
  • 板块CF25E Test
  • 楼主Masimly
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/5/29 14:30
  • 上次更新2024/5/29 17:36:16
查看原帖
第十一个数据RE 求助大佬
1160950
Masimly楼主2024/5/29 14:30
#include<iostream>
#include<string>
#include<cstring>
#define int long long
using namespace std;
const int N = 2e5 + 3;
string merge;
string major[6];
string temp;
int nexta[N], maxx = 0x3f3f3f3f;
void getnext(string s) {
	nexta[0] = -1;
	int len = s.size();
	int j = -1, i = 0;
	while (i < len) {
		if (j == -1 || major[i] == major[j]) {
			i++, j++;
			nexta[i] = j;
		}
		else {
			j = nexta[j];
		}
	}
}
int kmp(int pos1, int pos2, int bian) {
	getnext(major[pos2]);
	int i = 0, j = 0;
	int len1 = major[pos1].size();
	int len2 = major[pos2].size();
	while (i < len1) {
		if (j == -1 || major[pos1][i] == major[pos2][j]) {
			i++, j++;
		}
		else {
			j = nexta[j];
		}
		if (j == len2) return -1;
	}
	merge += major[pos1];
	merge += major[pos2].substr(j, len2);
	return 0;
}
void surgekmp(string surge, string orgin) {
	getnext(orgin);
	int i = 0, j = 0;
	int len1 = surge.size();
	int len2 = orgin.size();
	while (i < len1) {
		if (j == -1 || surge[i] == orgin[j]) {
			i++, j++;
		}
		else {
			j = nexta[j];
		}
		if (j == len2) { maxx = min(maxx, len1); return; }
	}
	maxx = min(maxx, len1 + len2 - j);
	return;
}
int cnt;
signed main() {
	major[1].resize(2e5);
	major[2].resize(2e5);
	major[3].resize(2e5);
	cin >> major[1];
	cin >> major[2];
	cin >> major[3];
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			if (j == i) {
				continue;
			}

			memset(nexta, 0, sizeof(nexta));
			merge.resize(2e6);
			merge = "";
			if (kmp(i, j, ++cnt) == -1) {
				merge = major[i];
			}
			memset(nexta, 0, sizeof(nexta));
			surgekmp(merge, major[6 - i - j]);
			memset(nexta, 0, sizeof(nexta));
			surgekmp(major[6 - i - j], merge);
		}
	}
	cout << maxx;
	return 0;
}
2024/5/29 14:30
加载中...