제출 #133076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133076		E869120	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	45 / 85	1551 ms	94092 KiB

necklace

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

const long long mod = 100000000007LL;

string S, T;
vector<long long> vec[3009];

long long power[3009]; bool nibeki[3009];

void init() {
	power[0] = 1LL;
	for (int i = 1; i <= 3000; i++) power[i] = (101LL * power[i - 1]);
	for (int i = 0; i <= 11; i++) nibeki[1 << i] = true;
}

long long hash_val(string &U) {
	long long r = 0;
	for (int i = 0; i < U.size(); i++) {
		r *= 101LL;
		r += (long long)(U[i] - 'a' + 1LL);
	}
	return r;
}

vector<long long> get_substring(string &U) {
	vector<long long> a, b, c;
	a.push_back(0);
	for (int i = 0; i < U.size(); i++) {
		a.push_back((101LL * a[a.size() - 1] + (long long)(U[i] - 'a' + 1)));
	}
	b.push_back(0);
	for (int i = U.size() - 1; i >= 0; i--) {
		b.push_back((b[b.size() - 1] + power[U.size() - 1 - i] * (long long)(U[i] - 'a' + 1)));
	}
	reverse(b.begin(), b.end());

	for (int i = 0; i < U.size(); i++) {
		long long s = a[i] + power[i] * b[i];
		c.push_back(s);
	}
	return c;
}

int main() {
	init();
	cin >> S >> T;
	for (int i = 0; i < S.size(); i++) {
		string G = "";
		for (int j = i + 1; j <= S.size(); j++) {
			if (S.size() > 400 || T.size() > 400) {
				if (nibeki[j - i] == false) continue;
			}
			G += S[j - 1];
			vector<long long> V1 = get_substring(G);
			for (int k = 0; k < V1.size(); k++) {
				vec[j - i].push_back((((V1[k] % mod) + mod) << 20) + 1LL * i);
			}
		}
	}
	for (int i = 0; i <= S.size(); i++) sort(vec[i].begin(), vec[i].end());

	int maxn = 0; pair<int, int> maxid = make_pair(-1, -1);
	for (int i = 0; i < T.size(); i++) {
		string G = "";
		for (int j = i + 1; j <= T.size(); j++) {
			G += T[j - 1];
			if (S.size() > 400 || T.size() > 400) {
				if (nibeki[j - i] == false) continue;
			}
			long long v = hash_val(G); v = (v % mod) + mod;

			int pos1 = lower_bound(vec[j - i].begin(), vec[j - i].end(), v << 20) - vec[j - i].begin();
			if (pos1 < vec[j - i].size() && (vec[j - i][pos1] >> 20) == v) {
				if (maxn < j - i) {
					maxn = j - i;
					maxid = make_pair(vec[j - i][pos1] % (1LL << 20), i);
				}
			}
		}
	}

	for (int i = 1; i <= T.size(); i++) {
		string G = "";
		for (int j = i - 1; j >= 0; j--) {
			G += T[j];
			if (S.size() > 400 || T.size() > 400) {
				if (nibeki[j - i] == false) continue;
			}
			long long v = hash_val(G); v = (v % mod) + mod;

			int pos1 = lower_bound(vec[i - j].begin(), vec[i - j].end(), v << 20) - vec[i - j].begin();
			if (pos1 < vec[i - j].size() && (vec[i - j][pos1] >> 20) == v) {
				if (maxn < i - j) {
					maxn = i - j;
					maxid = make_pair(vec[i - j][pos1] % (1LL << 20), j);
				}
			}
		}
	}

	cout << maxn << endl;
	cout << maxid.first << " " << maxid.second << endl;
	return 0;
}

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

necklace.cpp: In function 'long long int hash_val(std::__cxx11::string&)':
necklace.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < U.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp: In function 'std::vector<long long int> get_substring(std::__cxx11::string&)':
necklace.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < U.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < U.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp:53:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1; j <= S.size(); j++) {
                       ~~^~~~~~~~~~~
necklace.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < V1.size(); k++) {
                    ~~^~~~~~~~~~~
necklace.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= S.size(); i++) sort(vec[i].begin(), vec[i].end());
                  ~~^~~~~~~~~~~
necklace.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp:69:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1; j <= T.size(); j++) {
                       ~~^~~~~~~~~~~
necklace.cpp:77:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (pos1 < vec[j - i].size() && (vec[j - i][pos1] >> 20) == v) {
        ~~~~~^~~~~~~~~~~~~~~~~~~
necklace.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= T.size(); i++) {
                  ~~^~~~~~~~~~~
necklace.cpp:96:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (pos1 < vec[i - j].size() && (vec[i - j][pos1] >> 20) == v) {
        ~~~~~^~~~~~~~~~~~~~~~~~~

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