結果

問題 No.515 典型LCP
コンテスト
ユーザー pekempey
提出日時 2017-05-06 02:28:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,563 bytes
コンパイル時間 2,217 ms
コンパイル使用メモリ 184,356 KB
実行使用メモリ 98,792 KB
最終ジャッジ日時 2024-09-14 10:26:06
合計ジャッジ時間 6,588 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 15
権限があれば一括ダウンロードができます

ソースコード

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;
	for (int i = 0; i < n; i++) {
		start[i] = t.size();
		static char buf[800001];
		scanf("%s", buf);
		for (int j = 0; buf[j] != 0; j++) {
			t.push_back(buf[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;
		}
        if (x >= N) {
            x -= N;
        }
		ans += suf.getLcp(start[i], start[j]);
	}
	std::cout << ans << std::endl;

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