結果

問題 No.2454 Former < Latter
ユーザー Challestend RehtorbegnaroChallestend Rehtorbegnaro
提出日時 2023-09-01 21:58:51
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 120 ms / 2,000 ms
コード長 2,190 bytes
コンパイル時間 365 ms
コンパイル使用メモリ 44,768 KB
実行使用メモリ 36,132 KB
最終ジャッジ日時 2023-09-01 21:58:55
合計ジャッジ時間 3,164 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
11,248 KB
testcase_01 AC 3 ms
11,108 KB
testcase_02 AC 83 ms
36,072 KB
testcase_03 AC 86 ms
36,128 KB
testcase_04 AC 120 ms
36,128 KB
testcase_05 AC 114 ms
36,068 KB
testcase_06 AC 100 ms
36,132 KB
testcase_07 AC 87 ms
36,124 KB
testcase_08 AC 27 ms
11,328 KB
testcase_09 AC 35 ms
20,592 KB
testcase_10 AC 39 ms
20,716 KB
testcase_11 AC 85 ms
36,080 KB
testcase_12 AC 85 ms
36,072 KB
testcase_13 AC 83 ms
36,080 KB
testcase_14 AC 86 ms
36,064 KB
testcase_15 AC 46 ms
27,240 KB
testcase_16 AC 44 ms
25,120 KB
testcase_17 AC 47 ms
11,168 KB
testcase_18 AC 18 ms
11,120 KB
testcase_19 AC 65 ms
36,092 KB
testcase_20 AC 75 ms
36,072 KB
testcase_21 AC 26 ms
11,316 KB
testcase_22 AC 33 ms
18,524 KB
testcase_23 AC 34 ms
20,736 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <algorithm>
#define maxn 300000
#define maxlog 20

int T;
int n;
char s[maxn + 5];
int fst[maxn + 5], snd[maxn + 5], tnk[maxn + 5];
int sa[maxn + 5], rnk[2 * maxn + 5], het[maxn + 5][maxlog + 1], lg[maxn + 5];

inline int Stmin(int l, int r)
{
	int g = lg[r - l + 1];
	return std::min(het[l][g], het[r - (1 << g) + 1][g]);
}

int main()
{
	scanf("%d", &T);
	for (; T; --T)
	{
		scanf("%d", &n);
		scanf("%s", s + 1);
		for (int i = 1; i <= 26; ++i)
			tnk[i] = 0;
		for (int i = 1; i <= n; ++i)
			++tnk[fst[i] = s[i] - 'a' + 1];
		for (int i = 1; i <= 26; ++i)
			tnk[i] += tnk[i - 1];
		for (int i = n; i >= 1; --i)
			sa[tnk[fst[i]]--] = i;
		for (int k = 1, max = n; ; k <<= 1)
		{
			int cnt = 0;
			for (int i = n - k + 1; i <= n; ++i)
				snd[++cnt] = i;
			for (int i = 1; i <= n; ++i)
				if (sa[i] > k)
					snd[++cnt] = sa[i] - k;
			for (int i = 1; i <= max; ++i)
				tnk[i] = 0;
			for (int i = 1; i <= n; ++i)
				++tnk[fst[i]];
			for (int i = 1; i <= max; ++i)
				tnk[i] += tnk[i - 1];
			for (int i = n; i >= 1; --i)
				sa[tnk[fst[snd[i]]]--] = snd[i];
			for (int i = 1; i <= n; ++i)
				snd[i] = fst[i];
			fst[sa[1]] = cnt = 1;
			for (int i = 2; i <= n; ++i)
				fst[sa[i]] = snd[sa[i]] == snd[sa[i - 1]] && snd[sa[i] + k] == snd[sa[i - 1] + k] ? cnt : ++cnt;
			if (cnt == n)
				break;
			else
				max = cnt;
		}
		for (int i = 1; i <= n; ++i)
			rnk[sa[i]] = i;
		for (int i = 1, j = 0; i <= n; ++i)
			if (rnk[i] > 1)
			{
				j && (--j);
				int pos = sa[rnk[i] - 1];
				for (; i + j <= n && pos + j <= n && s[i + j] == s[pos + j]; ++j);
				het[rnk[i]][0] = j;
			}
		for (int j = 1, p = 2; p <= n; ++j, p <<= 1)
			for (int i = 1; i + p - 1 <= n; ++i)
				het[i][j] = std::min(het[i][j - 1], het[i + (p >> 1)][j - 1]);
		for (int i = 2; i <= n; ++i)
			lg[i] = lg[i >> 1] + 1;
		int ans = 0;
		for (int i = 1; i < n; ++i)
		{
			int lcp = Stmin(std::min(rnk[1], rnk[i + 1]) + 1, std::max(rnk[1], rnk[i + 1]));
			ans += (lcp < i && lcp < n - i && s[1 + lcp] < s[(i + 1) + lcp]) || (lcp >= i && i < n - i);
		}
		printf("%d\n", ans);
	}
	return 0;
}
0