結果

問題 No.2454 Former < Latter
コンテスト
ユーザー Challestend Rehtorbegnaro
提出日時 2023-09-01 21:58:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 138 ms / 2,000 ms
コード長 2,190 bytes
コンパイル時間 480 ms
コンパイル使用メモリ 42,204 KB
実行使用メモリ 33,536 KB
最終ジャッジ日時 2025-01-03 08:32:12
合計ジャッジ時間 3,022 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:20:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   20 |         scanf("%d", &T);
      |         ~~~~~^~~~~~~~~~
main.cpp:23:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   23 |                 scanf("%d", &n);
      |                 ~~~~~^~~~~~~~~~
main.cpp:24:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   24 |                 scanf("%s", s + 1);
      |                 ~~~~~^~~~~~~~~~~~~

ソースコード

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