제출 #862362

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862362		iskhakkutbilim	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	47 ms	348 KiB

necklace

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

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 101;

vector<int> z_function(string s){
	int n =(int)s.size();
	vector<int> z(n);
	for(int i=1, l=0, r=0; i<n; ++i){
		if(i <= r)
			z[i] = min (r-i+1, z[i-l]);
		while(i+z[i] < n && s[z[i]] == s[i+z[i]])
			++z[i];
		if(i+z[i]-1 > r)
			l = i,  r = i+z[i]-1;
	}
	return z;
}

int has_sub(string a, string b){
	vector<int> z = z_function(b + "#" + a);
	for(int i = b.size() + 1; i < z.size(); i++){
		if(z[i] >= b.size()) return 1;
	}
	return 0;
}


int good(string a, string b){
	if(has_sub(a + a, b)) return 1;
	reverse(all(a));
	if(has_sub(a + a, b)) return 1;
	return 0;
}




string s, t;
int PA[N + 1][26], PB[N+1][26];
int n,m;
int getA(int l, int r, char ch){
	return PA[r][ch]-(l > 0 ? PA[l-1][ch] : 0);	
}

int getB(int l, int r, int ch){
	return PB[r][ch]-(l > 0 ? PB[l-1][ch] : 0);	
}

main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> s >> t;
	n = s.size();
	m = t.size();
	for(int i = 0;i < n; i++){
		for(int j = 0;j < 26; j++){
			PA[i][j] = (i > 0 ? PA[i-1][j] : 0);
			if(s[i]-'a' == j) PA[i][j]++;
		}
	}
	for(int i = 0;i < m; i++){
		for(int j = 0;j < 26; j++){
			PB[i][j] = (i > 0 ? PB[i-1][j] : 0);
			if(t[i]-'a' == j) PB[i][j]++;
		}
	}
	int ans = 0;
	pair<int, int> start = {-1, -1};
	
	
	for(int len = 1; len <= min(n, m); len++){
		string A = "";
		for(int idx = 0; idx < len; idx++) A+= s[idx];
		for(int i = 0;i + len-1 < n && ans < len; i++){
			string B = "";
			for(int idx = 0; idx < len; idx++) B+= t[idx];
			for(int j = 0;j + len-1 < m && ans < len; j++){
				
				if(good(A, B)){
					ans = len;
					start = {i, j};
					break;
				}
				B.erase(B.begin());
				if(j + len < n) B.push_back(t[j + len]);
			}
			if(i + len < n)A.push_back(s[i + len]);
			A.erase(A.begin());
		}
	}
	cout << ans << '\n';
	cout << start.ff << ' ' << start.ss;
	return 0;
}

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

necklace.cpp: In function 'int has_sub(std::string, std::string)':
necklace.cpp:25:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = b.size() + 1; i < z.size(); i++){
      |                            ~~^~~~~~~~~~
necklace.cpp:26:11: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   if(z[i] >= b.size()) return 1;
necklace.cpp: In function 'int getA(int, int, char)':
necklace.cpp:46:15: warning: array subscript has type 'char' [-Wchar-subscripts]
   46 |  return PA[r][ch]-(l > 0 ? PA[l-1][ch] : 0);
      |               ^~
necklace.cpp:46:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   46 |  return PA[r][ch]-(l > 0 ? PA[l-1][ch] : 0);
      |                                    ^~
necklace.cpp: At global scope:
necklace.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main(){
      | ^~~~

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