Submission #522808

#	Time	Username	Problem	Language	Result	Execution time	Memory
522808		LucaDantas	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	3 ms	332 KiB

necklace

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 3010, p = 31;
constexpr long long mod = 4000000007;

struct StringHash {
	string s;

	long long a[maxn], pot[maxn];

	void build() {
		int n = (int)s.size();
		a[0] = s[0]-'a';
		pot[0] = 1;
		
		for(int i = 1; i < maxn; i++)
			pot[i] = pot[i-1] * p % mod;

		for(int i = 1; i < n; i++)
			a[i] = (a[i-1]*p + (s[i]-'a')) % mod; 
	}

	long long get(int l, int r) {
		return ( a[r] - (l ? a[l-1]*pot[r-l+1]%mod : 0) + mod ) % mod;
	}
} A, B;

int main() {
	cin >> A.s >> B.s;

	pair<int, pair<int,int>> ans = {-1, {-1, -1}};

	A.build();
	for(int SLA = 0; SLA < 2; SLA++) {
		B.build();
		for(int l = 0; l < (int)A.s.size(); l++) {
			for(int r = 0; r < (int)B.s.size(); r++) {
				if(A.s[l] != B.s[r]) continue;
				
				int sz1 = 0, sz2 = 0;
				
				for(int lg = 12; lg >= 0; lg--) {
					sz1 += 1<<lg;

					if(l+sz1-1 >= A.s.size() ||
						r+sz1-1 >= B.s.size() ||
							A.get(l, l+sz1-1) != B.get(r, r+sz1-1))
							sz1 -= 1<<lg;
				}

				for(int lg = 12; lg >= 0; lg--) {
					sz2 += 1<<lg;
					if(l+sz1+sz2-1 >= A.s.size() ||
						r-sz2 < 0 ||
							A.get(l+sz1, l+sz1+sz2-1) != B.get(r-sz2, r-1))
							sz2 -= 1<<lg;
				}

				ans = max(ans, {sz1+sz2, {l, r-sz2}});
			}
		}
		reverse(B.s.begin(), B.s.end());
	}

	printf("%d\n%d %d\n", ans.first, ans.second.first, ans.second.second);
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:46:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |      if(l+sz1-1 >= A.s.size() ||
      |         ~~~~~~~~^~~~~~~~~~~~~
necklace.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |       r+sz1-1 >= B.s.size() ||
      |       ~~~~~~~~^~~~~~~~~~~~~
necklace.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |      if(l+sz1+sz2-1 >= A.s.size() ||
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~

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