Wa on #3
  • 板块CF25E Test
  • 楼主zlttcl
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/26 13:46
  • 上次更新2024/7/26 14:53:03
查看原帖
Wa on #3
555381
zlttcl楼主2024/7/26 13:46
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
char s[4][N];
int ans, len[4], kmp[4][N];
inline ll read(){
	ll x = 0, m = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') m = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * m;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		write(-x);
		return;
	}
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
inline void solve(){
	for(int x = 1; x <= 3; ++ x){
		int j = 0;
		for(int i = 2; i <= len[x]; ++ i){
			while(j && s[x][i] != s[x][j + 1]) j = kmp[x][j];
			if(s[x][i] == s[x][j + 1]) ++ j;
			kmp[x][i] = j;
		}
	}
}
inline int get(int a, int b, int c){
	int len1 = len[a], len2 = len[b], len3 = len[c];
	int p1 = 0;
	for(int i = 1; i <= len1; ++ i){
		while(p1 && s[b][p1 + 1] == s[a][i]) p1 = kmp[b][p1];
		if(s[b][p1 + 1] == s[a][i]) ++ p1;
		if(p1 == len2){
			p1 = -1;
			break;
		}
	}
	if(p1 == -1){
		int p = 0;
		for(int i = 1; i <= len1; ++ i){
			while(p && s[c][p + 1] != s[a][i]) p = kmp[c][p];
			if(s[c][p + 1] == s[a][i]) ++ p;
			if(p == len3){
				p = -1;
				break;
			}
		}
		if(p == -1) return len1;
		else return len1 + len3 - p;
	}
	int p = 0;
	for(int i = 1; i <= len1; ++ i){
		while(p && s[c][p + 1] != s[a][i]) p = kmp[c][p];
		if(s[c][p + 1] == s[a][i]) ++ p;
		if(p == len3){
			p = -1;
			break;
		}
	}
	if(p == -1) return len1 + len2 - p1;
	int p2 = p;
	for(int i = p1 + 1; i <= len2; ++ i){
		while(p2 && s[c][p2 + 1] == s[b][i]) p2 = kmp[c][p2];
		if(s[c][p2 + 1] == s[b][i]) ++ p2;
		if(p2 == len3){
			p2 = -1;
			break;
		}
	}
	if(p2 == -1) return len1 + len2 - p1;
	else return len1 + len2 + len3 - p1 - p2;
}
signed main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
    scanf("%s%s%s", s[1] + 1, s[2] + 1, s[3] + 1);
    for(int i = 1; i <= 3; ++ i) len[i] = strlen(s[i] + 1);
    solve();
    ans = min(get(1, 2, 3), get(1, 3, 2));
    ans = min(ans, min(get(2, 1, 3), get(2, 3, 1)));
    ans = min(ans, min(get(3, 1, 2), get(3, 2, 1)));
    write(ans);
	return 0;
}


2024/7/26 13:46
加载中...