#include<bits/stdc++.h> #define ll long long #define ld long double #define N 1000005 #define Orz ios::sync_with_stdio(0),cin.tie(0) #define INF 2e18 #define rep(i,l,r) for(int i=l;i<=r;i++) #define pii pair<int,int> #define x first #define y second usingnamespace std; int n,m,Z[2*N]; bool ans[2*N]; char S[2*N],T[N]; //T原字串、S插入點字串
voidLongest(){ n = strlen(T);m = 2*n+1; memset(S,'.',m); for(int i=0;i<n;i++)S[2*i+1] = T[i]; Z[0] = 1; int l = 0,r = 0; for(int i=1;i<m;i++){ Z[i] = max(min(Z[2*l-i],r-i),1); while(i-Z[i]>=0 && i+Z[i] < m && S[i+Z[i]]==S[i-Z[i]]){ l = i;r = i+Z[i]; Z[i]++; } } }