結果

問題 No.515 典型LCP
ユーザー pekempeypekempey
提出日時 2017-05-06 00:38:36
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,430 bytes
コンパイル時間 1,055 ms
コンパイル使用メモリ 84,960 KB
実行使用メモリ 44,828 KB
最終ジャッジ日時 2023-10-12 11:15:44
合計ジャッジ時間 8,126 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 405 ms
27,456 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,352 KB
testcase_05 AC 469 ms
44,280 KB
testcase_06 AC 706 ms
43,976 KB
testcase_07 AC 621 ms
44,676 KB
testcase_08 AC 769 ms
44,264 KB
testcase_09 AC 312 ms
26,856 KB
testcase_10 AC 318 ms
27,084 KB
testcase_11 AC 318 ms
27,564 KB
testcase_12 AC 317 ms
26,864 KB
testcase_13 AC 257 ms
26,872 KB
testcase_14 AC 50 ms
26,896 KB
testcase_15 AC 329 ms
44,556 KB
testcase_16 AC 328 ms
43,792 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

class SuffixDataStructure {
public:
	// a[i]>=0
	SuffixDataStructure(const std::vector<int> &a) : a(a) {
		sa = sufarray(a);
		buildLcp();
		buildRmq();
	}

	int getLcp(int i, int j) {
		if (i == j) {
			return a.size() - std::max(i, j);
		}
		i = isa[i];
		j = isa[j];
		if (i > j) {
			std::swap(i, j);
		}
		i += rmqN;
		j += rmqN;
		int val = lcp.size();
		while (i < j) {
			if (i & 1) {
				val = std::min(val, rmq[i++]);
			}
			if (j & 1) {
				val = std::min(val, rmq[--j]);
			}
			i /= 2;
			j /= 2;
		}
		return val;
	}

private:
	const std::vector<int> &a;
	std::vector<int> sa;
	std::vector<int> isa;
	std::vector<int> lcp;
	std::vector<int> rmq;
	int rmqN;

	std::vector<int> sufarray(std::vector<int> a) {
		const int TYPE_S = -1;
		const int TYPE_L = -2;
		const int n = a.size();
		if (n == 1) {
			return std::vector<int>(1);
		}
		std::vector<int> type(n);
		type.back() = TYPE_S;
		for (int i = n - 2; i >= 0; i--) {
			if (a[i] < a[i + 1]) {
				type[i] = TYPE_S;
			} else if (a[i] > a[i + 1]) {
				type[i] = TYPE_L;
			} else {
				type[i] = type[i + 1];
			}
		}
		std::vector<int> lmsID;
		std::vector<std::vector<int>> lms;
		int prev = n;
		for (int i = n - 1; i >= 1; i--) {
			if (type[i - 1] == TYPE_L && type[i] == TYPE_S) {
				type[i] = lmsID.size();
				lmsID.push_back(i);
				lms.emplace_back(std::vector<int>(a.begin() + i, a.begin() + prev));
				prev = i;
			}
		}
		auto inducedSort = [&](const std::vector<int> &a, const std::vector<int> &ordSS, const std::vector<int> &type) {
			const int n = a.size();
			const int maxi = *std::max_element(a.begin(), a.end());
			std::vector<int> sa(n, -1), L(maxi + 2), S(maxi + 2);
			for (int i = 0; i < n; i++) {
				L[a[i] + 1]++;
			}
			for (int i = 0; i < L.size() - 1; i++) {
				L[i + 1] += L[i];
				S[i] = L[i + 1];
			}
			for (int i = ordSS.size() - 1; i >= 0; i--) {
				int j = ordSS[i];
				sa[--S[a[j]]] = j;
			}
			for (int i = 0; i < L.size() - 1; i++) {
				S[i] = L[i + 1];
			}
			for (int i = 0; i < n; i++) {
				const int j = sa[i] - 1;
				if (j >= 0 && type[j] == TYPE_L) {
					sa[L[a[j]]++] = j;
				}
			}
			for (int i = n - 1; i >= 0; i--) {
				const int j = sa[i] - 1;
				if (j >= 0 && (type[j] == TYPE_S || type[j] >= 0)) {
					sa[--S[a[j]]] = j;
				}
			}
			return sa;
		};
		const int SS = lmsID.size();
		std::vector<int> ordLms;
		for (int i : inducedSort(a, lmsID, type)) {
			if (type[i] >= 0) {
				ordLms.push_back(i);
			}
		}
		std::reverse(lmsID.begin(), lmsID.end());
		std::vector<int> rankLms(SS);
		for (int i = 1; i < SS; i++) {
			const int x = type[ordLms[i - 1]];
			const int y = type[ordLms[i]];
			rankLms[i] = rankLms[i - 1] + (lms[x] < lms[y]);
		}
		for (int i = 0; i < SS; i++) {
			type[ordLms[i]] = rankLms[i];
		}
		std::vector<int> lmsA;
		for (int i : lmsID) {
			lmsA.push_back(type[i]);
		}
		std::vector<int> ordSS;
		for (int i : sufarray(lmsA)) {
			ordSS.push_back(lmsID[i]);
		}
		return inducedSort(a, ordSS, type);
	}

	void buildLcp() {
		const int n = a.size() - 1;
		isa.resize(n + 1);
		lcp.assign(n + 1, 0);
		for (int i = 0; i <= n; i++) {
			isa[sa[i]] = i;
		}
		int k = 0;
		for (int i = 0; i < n; i++) {
			int j = sa[isa[i] - 1];
			k = std::max(0, k - 1);
			while (i + k < n && j + k < n && a[i + k] == a[j + k]) {
				k++;
			}
			lcp[isa[i] - 1] = k;
		}
	}

	void buildRmq() {
		rmqN = 1;
		while (rmqN < lcp.size()) {
			rmqN *= 2;
		}
		rmq.assign(rmqN * 2, lcp.size());
		for (int i = 0; i < lcp.size(); i++) {
			rmq[i + rmqN] = lcp[i];
		}
		for (int i = rmqN - 1; i >= 1; i--) {
			rmq[i] = std::min(rmq[i * 2], rmq[i * 2 + 1]);
		}
	}
};

int main() {
	int n;
	std::cin >> n;

	std::vector<int> start(n);
	std::vector<int> len(n);
	std::vector<int> t;
	for (int i = 0; i < n; i++) {
		start[i] = t.size();
		static char buf[100001];
		scanf("%s", buf);
		int j;
		for (j = 0; buf[j] != 0; j++) {
			t.push_back(buf[j]);
		}
		len[i] = j;
	}
	t.push_back(0);

	SuffixDataStructure suf(t);

	int m, x, d;
	std::cin >> m >> x >> d;

	long long ans = 0;
	for (int k = 0; k < m; k++) {
		int i = (x / (n - 1)) + 1;
		int j = (x % (n - 1)) + 1;
		if (i > j) {
			std::swap(i, j);
		} else {
			j = j + 1;
		}
		x = (x + d) % (1LL * n * (n - 1));
		i--;
		j--;
		ans += std::min(suf.getLcp(start[i], start[j]), std::min(len[i], len[j]));
	}
	std::cout << ans << std::endl;
}
0