C题数据出大锅
C题数据也太水了吧 直接匹配完前后缀 不用看是否为回文串也能过啊? 而且赛时就是这样过的
补题代码 20ms 就水过去了
#include<bits/stdc++.h> #define endl '\n' #define GG() void(cout<<"-1\n") #define YES() void(cout << "YES\n") #define NO() void(cout << "NO\n") #define debug(x) void (cout<<x<<"\n") #define dbug(x,y); cout<<x<<' '<<y<<endl; #define fi first #define se second using namespace std; typedef long long LL; typedef pair<int, int> PII; const int INF = 0x3f3f3f3f, N = 2e5 + 10, mod1 = 1e9+7,mod2=954169327; const LL inf = 1e9+10; const int M = 2 * N; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b) { return a * b / gcd(a, b); } int n,m; int a[N]; LL P[N],ha[2][N]; LL qr(int id,int l,int r,int MOD) { return (ha[id][r]-ha[id][l-1]*P[r-l+1]%MOD+MOD)%MOD; } void solve() { srand(time(0)); int MOD = 998244353 + rand() % 10007; int BASE = 33 + rand() % 233; P[0]=1; string s1,s2; cin>>n>>m; cin>>s1>>s2; for (int i = 1; i <= N-10; i++) P[i] = P[i - 1] * BASE % MOD; for (int i = 1; i <=n; i++) { ha[0][i] = (ha[0][i-1] * BASE + s1[i-1]-'a'+1) % MOD; //cout<<ha[0][i]<<endl; } for(int i = 1;i<=m;i++) { ha[1][i] = (ha[1][i-1]*BASE + s2[i-1]-'a'+1)%MOD; } vector<LL>mx(m+4); for(int i =1;i<=m;i++) { mx[i]=mx[i-1]; if(n-i+1<1) continue; if(qr(1,1,i,MOD)==qr(0,n-i+1,n,MOD)) mx[i]=i; //cout<<qr(1,1,i,MOD)<<' '<<qr(0,n-i+1,n,MOD); //cout<<' '<<i<<' '<<mx[i]<<endl; } LL res=-1; for(int i =1;i<=n;i++) { if(m-i+1<1) break; if(qr(0,1,i,MOD)==qr(1,m-i+1,m,MOD)) { if(mx[min(m-i,n-i)]!=0) { res=max(res,((LL)i+mx[min(m-i,n-i)])*2ll); // cout<<i<<' '<<m-i<<' '<<n-i<<' '<<mx[min(m-i,n-i)]<<endl; } } } cout<<res<<endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int xzx_123 = 1; //cin >> xzx_123; while (xzx_123--) solve(); return 0; }
hack数据 答案是-1 跑出来是8 这能过就离谱
5 5 abcde cdeba