結果

問題 No.515 典型LCP
ユーザー pekempeypekempey
提出日時 2017-05-06 02:32:49
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 580 ms / 1,000 ms
コード長 4,699 bytes
コンパイル時間 2,358 ms
コンパイル使用メモリ 184,476 KB
実行使用メモリ 98,864 KB
最終ジャッジ日時 2024-09-14 10:28:26
合計ジャッジ時間 7,902 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 580 ms
96,128 KB
testcase_01 AC 394 ms
93,492 KB
testcase_02 AC 237 ms
88,012 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 311 ms
98,864 KB
testcase_06 AC 306 ms
92,440 KB
testcase_07 AC 302 ms
95,536 KB
testcase_08 AC 341 ms
98,528 KB
testcase_09 AC 165 ms
88,700 KB
testcase_10 AC 161 ms
88,032 KB
testcase_11 AC 160 ms
88,064 KB
testcase_12 AC 160 ms
88,000 KB
testcase_13 AC 162 ms
87,752 KB
testcase_14 AC 105 ms
87,900 KB
testcase_15 AC 288 ms
95,636 KB
testcase_16 AC 295 ms
94,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

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];
        int k = std::__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() {
	clock_t beg = clock();
	int n;
	std::cin >> n;

	std::vector<int> start(n);
	std::vector<int> t;
    std::vector<int> len(n);
	for (int i = 0; i < n; i++) {
		start[i] = t.size();
		static char buf[800001];
		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);
	clock_t end = clock();
	std::cerr << (double)(end - beg) / CLOCKS_PER_SEC << std::endl;

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

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

	clock_t end2 = clock();
	std::cerr << (double)(end2 - beg) / CLOCKS_PER_SEC << std::endl;
}
0