#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 410;
const ll mod = 1e9+7;
const ll mod2 = 69696959;
const ld PI = acos((ld)-1);
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
string S , T;
int n , m;
const int base = 31;
const int base2 = 47;
struct hsh{
string s, sr;
int pw[maxn];
int h[maxn];
int pw2[maxn];
int h2[maxn];
int n;
void init(string S){
s = S;
pw[0] = 1;
pw2[0] = 1;
for(int i = 1 ; i < maxn ; i ++){
pw[i] = (pw[i - 1] * 1LL * base)%mod;pw2[i] = (pw2[i - 1] * 1LL * base2)%mod2;
}
n = s.size();
s = "9" + s;
for(int i = 1 ; i <= n ; i ++)
h[i] = (h[i - 1] * 1LL * base + (s[i] - 'a' + 1))%mod,
h2[i] = (h2[i - 1] * 1LL * base2 + (s[i] - 'a' + 1))%mod2;
}
ll get(int l , int r){
if(l > r)return(0);
int H1 = (h[r] * 1LL - (h[l - 1] * 1LL * pw[r - l + 1])%mod + mod)%mod;
return(H1);
}
ll get2(int l , int r){
if(l > r)return(0);
int H2 = (h2[r] * 1LL - (h2[l - 1] * 1LL * pw2[r - l + 1])%mod2 + mod2)%mod2;
return(H2);
}
}s , t , tr;
unordered_set < ll > st;
bool solve(int x){
st.clear();
for(int i = 1 ; i <= n - x + 1 ; i ++){
for(int j = 0 ; j < x ; j ++){
ll res = s.get(i , i + x - 1 - j);
res = (res * 1LL + s.get(i + x - j, i + x - 1) * 1LL * s.pw[x - j])%mod;
ll res2 = s.get2(i , i + x - 1 - j);
res2 = (res2 * 1LL + s.get2(i + x - j, i + x - 1) * 1LL * s.pw2[x - j])%mod2;
st.insert((res << 32LL)|res2);
}
}
for(int i = 1 ; i <= m - x + 1 ; i ++){
if(st.count((t.get(i , i + x - 1) << 32LL)| t.get2(i , i + x - 1)))return(1);
if(st.count((tr.get(i , i + x - 1) << 32LL)| tr.get2(i , i + x - 1)))return(1);
}
return(0);
}
int32_t main(){
migmig;
cin >> S >> T;
s.init(S);
t.init(T);
reverse(T.begin() , T.end());
tr.init(T);
n = S.size() , m = T.size();
n = S.size() , m = T.size();
for(int i = min(n , m) ; i > 0 ; i --)if(solve(i))dokme(i);
return(0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
