제출 #377237

#제출 시각아이디문제언어결과실행 시간메모리
377237soroushNecklace (Subtask 1-3) (BOI19_necklace1)C++17
0 / 85
2 ms364 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...