結果

問題 No.515 典型LCP
ユーザー pekempeypekempey
提出日時 2017-05-06 00:10:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,428 bytes
コンパイル時間 1,327 ms
コンパイル使用メモリ 87,436 KB
実行使用メモリ 98,552 KB
最終ジャッジ日時 2024-09-14 10:06:07
合計ジャッジ時間 5,819 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 AC 212 ms
88,164 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 304 ms
98,552 KB
testcase_06 AC 307 ms
93,352 KB
testcase_07 AC 311 ms
95,972 KB
testcase_08 AC 341 ms
98,264 KB
testcase_09 AC 155 ms
88,516 KB
testcase_10 AC 158 ms
87,556 KB
testcase_11 AC 151 ms
88,004 KB
testcase_12 AC 162 ms
87,672 KB
testcase_13 AC 160 ms
88,308 KB
testcase_14 AC 102 ms
87,936 KB
testcase_15 AC 281 ms
96,000 KB
testcase_16 AC 287 ms
94,308 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);
		}
		int k = lg[j - i];
		return std::min(rmq[k][i], rmq[k][j - (1 << k)]);
	}

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

	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() {
		const int n = lcp.size();
		lg.resize(n + 1);
		for (int i = 2; i <= n; i++) {
			lg[i] = lg[i / 2] + 1;
		}
		const int m = lg[n];
		rmq.assign(m + 1, std::vector<int>(n));
		for (int i = 0; i < n; i++) {
			rmq[0][i] = lcp[i];
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j + (1 << i) < n; j++) {
				rmq[i + 1][j] = std::min(rmq[i][j], rmq[i][j + (1 << i)]);
			}
		}
	}
};

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