训练串串题

//卡空间，不能开 long long
const int maxn = 2e6 + 7;
 
int fail[maxn], Tree[maxn][26];
string S, T;
int n, m, q;
 
signed main() {
//	freopen("saki.in", "r", stdin);
//	freopen("saki.out", "w", stdout);
	
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
 
	
	cin >> S;
	n = S.size(); S = "~" + S;
	F(i, 0, n - 1) {
		Tree[i][S[i + 1] - 'a'] = i + 1;
		F(j, 0, 25) {
			if(j == S[i + 1] - 'a' && i >= 1) fail[Tree[i][j]] = Tree[fail[i]][j];
			else Tree[i][j] = Tree[fail[i]][j];
		}
	}
	cin >> q;
	F(_, 1, q) {
		cin >> T; m = T.size();
		F(i, n, n + m - 1) {
			Tree[i][T[i - n] - 'a'] = i + 1;
			F(j, 0, 25) {
				if(j == T[i - n] - 'a') fail[Tree[i][j]] = Tree[fail[i]][j];
				else Tree[i][j] = Tree[fail[i]][j];
			}
		}
		F(i, n + 1, n + m) cout << fail[i] << " "; cout << '\n';
	}
 
    return 0;
}

const int maxn = 1e6 + 7;
const int mod1 = 1e9 + 21, mod2 = 1e9 + 87;

string S;
int n;
int H1[maxn], H2[maxn], P1[maxn], P2[maxn];

inline pii Get(int l, int r) { return {(H1[r] + mod1 - H1[l - 1] * P1[r - l + 1] % mod1) % mod1, (H2[r] + mod2 - H2[l - 1] * P2[r - l + 1] % mod2) % mod2}; }

inline bool check(int l, int r) {
	pii ret1 = Get(1, l - 1), ret2 = Get(l, r - 1), ret3 = Get(r, n);
	return ( ((ret1.fi + ret2.fi) % mod1 == ret3.fi) && ((ret1.se + ret2.se) % mod2 == ret3.se) );
}

inline bool No0(int l, int r) { return (S[l] == '0' ? l == r : 1); }
inline bool chk(int l, int r) { return ((l <= 1) ? 0 : (check(l, r) && No0(1, l - 1) && No0(l, r - 1) && No0(r, n))); }
inline void Print(int l, int r) { F(i, 1, l - 1) cout << S[i]; cout << '+'; F(i, l, r - 1) cout << S[i]; cout << '='; F(i, r, n) cout << S[i]; }

signed main() {
//	freopen("saki.in", "r", stdin);
//	freopen("saki.out", "w", stdout);
	
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> S;
	n = S.size();
	P1[0] = P2[0] = 1;
	S = "#" + S;
	F(i, 1, n) P1[i] = (P1[i - 1] * 10) % mod1, P2[i] = (P2[i - 1] * 10) % mod2;
	F(i, 1, n) H1[i] = (H1[i - 1] * 10 + S[i] - '0') % mod1, H2[i] = (H2[i - 1] * 10 + S[i] - '0') % mod2;
	F(i, (n / 3), (n >> 1)) {
		if(chk(i, n - i + 1)) { Print(i, n - i + 1); return 0; }
		if(chk(i + 1, n - i + 1)) { Print(i + 1, n - i + 1); return 0; }
		if(chk(n - (i << 1) + 2, n - i + 1)) { Print(n - (i << 1) + 2, n - i + 1); return 0; }
		if(chk(n - (i << 1) + 1, n - i + 1)) { Print(n - (i << 1) + 1, n - i + 1); return 0; }
	}

    return 0;
}

const int maxn = 8e6 + 7;

char S[maxn], tmp[maxn];
int n;
int p[maxn];

inline void MLC() {
	int tot = -1;
	F(i, 0, n) { tmp[++tot] = S[i]; tmp[++tot] = '#'; }
	n = tot; 
	F(i, 0, n) S[i] = tmp[i];
	int R = 0, mid = 0;
	F(i, 1, n) {
		if(i <= R) p[i] = min(p[(mid << 1) - i], R - i + 1);
		else p[i] = 1;
		while(S[i + p[i]] == S[i - p[i]]) p[i]++;
		if(i + p[i] - 1 >= R) R = i + p[i] - 1, mid = i;
	}
}

signed main() {
//	freopen("saki.in", "r", stdin);
//	freopen("saki.out", "w", stdout);
	
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> S + 1; 
	n = strlen(S + 1); 
	S[0] = '~';
	MLC();
	int L = 1, R = n;
	F(i, 1, n) {
		if(S[i] != '#') continue ;
		if(i - p[i] + 1 <= L) L = i;
	}
	Fdn(i, n, L + 1) {
		if(S[i] != '#') continue ;
		if(i + p[i] - 1 >= R) R = i;
	}
	cout << ((R - L) >> 1);


    return 0;
}