Submission #377237

#	Time	Username	Problem	Language	Result	Execution time	Memory
377237		soroush	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	2 ms	364 KiB

necklace

#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);
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40