제출 #530112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530112		fatemetmhr	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	45 / 85	1557 ms	584 KiB

necklace

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb     push_back
#define fi     first
#define se     second
#define all(x) x.begin(), x.end()

const int maxn5 = 7e3 + 10;

int n, m;

string z;
vector <pair<int, int>> av, qu;
int l[maxn5], lp[maxn5], lcp[maxn5];


inline void find_lcp(){
	int n = z.size();
	fill(lcp, lcp + n, 0);
	int l = 0, r = 0;
	//cout << "alright " << z << endl;
	for(int i = 1; i < n; i++){
		if(i <= r)
			lcp[i] = min(r - i + 1, lcp[i - l]);
		//cout << i << ' ' << l << ' ' << r << ' ' << lcp[i] << endl;
		while(i + lcp[i] < n && z[lcp[i]] == z[i + lcp[i]])
			lcp[i]++;
		if(i + lcp[i] - 1 > r){
			l = i;
			r = i + lcp[i] - 1;
		}
		//cout << i << ' ' << lcp[i] << endl;
	}
	return;
}

inline pair<int, pair<int, int>> solve(string s, string t){
	
	//cout << "wow! " << endl;
	n = s.size(); 
	m = t.size();
	string sp = s;
	reverse(sp.begin(), sp.end());
	
	
	int ans = 0, idt, ids;
	
	for(int i = 0; i < m; i++){
		qu.clear();
		av.clear();
		z = "";
		for(int j = i; j < m; j++)
			z.pb(t[j]);
		z = z + "$";
		int id = z.size();
		z = z +  s;
		find_lcp();
		for(int j = 0; j < n; j++)
			l[j] = lcp[j + id];
		z = "";
		for(int j = i - 1; j >= 0; j--)
			z.pb(t[j]);
		z = z + "$";
		id = z.size();
		z = z + sp;
		find_lcp();
		for(int j = 0; j < n; j++)
			lp[j] = lcp[n - j - 1 + id];
		for(int j = 0; j < n; j++){
			//cout << i << ' ' << j << ' ' << l[j] << ' ' << lp[j] << endl;
			qu.pb({l[j] + j, j});
			av.pb({j - lp[j] + 1, j});
		}
		sort(all(qu));
		sort(all(av));
		int ind = 0, mx = -1;
		for(auto [val, id] : qu){
			while(ind < av.size() && av[ind].fi <= val){
				mx = max(mx, av[ind].se);
				ind++;
			}
			if(mx - id + 1 >= ans && mx - id + 1 >= 1){
				ans = mx - id + 1;
				ids = id;
				if(val - id >= ans)
					idt = i;
				else
					idt = i + val - id - 1 - (mx - id + 1) + 1;
			}
		}
	}
	
	return {ans, {ids, idt}};
}


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	

	string s, t; cin >> s >> t;

	pair <int, pair<int, int>> ans1 = solve(s, t);
	if(true){
		reverse(t.begin(), t.end());
		pair <int, pair<int, int>> ans2 = solve(s, t);
		int len = ans2.fi, id = ans2.se.se;
		id = int(t.size()) - id - 1;
		id -= len - 1;
		ans2.se.se = id;
		if(ans1 < ans2)
			ans1 = ans2;
	}
	

	cout << ans1.fi << '\n' << ans1.se.fi << ' ' << ans1.se.se << '\n';

	
}

컴파일 시 표준 에러 (stderr) 메시지

necklace.cpp: In function 'std::pair<int, std::pair<int, int> > solve(std::string, std::string)':
necklace.cpp:82:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    while(ind < av.size() && av[ind].fi <= val){
      |          ~~~~^~~~~~~~~~~
necklace.cpp:97:25: warning: 'ids' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |  return {ans, {ids, idt}};
      |                         ^
necklace.cpp:97:25: warning: 'idt' may be used uninitialized in this function [-Wmaybe-uninitialized]

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