結果
| 問題 |
No.2454 Former < Latter
|
| コンテスト | |
| ユーザー |
 kakel-san
|
| 提出日時 | 2023-09-01 23:13:08 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 147 ms / 2,000 ms |
| コード長 | 7,410 bytes |
| コンパイル時間 | 1,209 ms |
| コンパイル使用メモリ | 110,592 KB |
| 実行使用メモリ | 31,488 KB |
| 最終ジャッジ日時 | 2025-01-03 11:26:14 |
| 合計ジャッジ時間 | 4,549 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 23 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
class Program
{
static int NN => int.Parse(ReadLine());
static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
public static void Main()
{
Solve();
}
static void Solve()
{
var t = NN;
var ans = new int[t];
for (var u = 0; u < t; ++u)
{
var n = NN;
var s = ReadLine();
ans[u] = Former(s);
}
WriteLine(string.Join("\n", ans));
}
static int Former(string s)
{
var sa = SuffixArray(s);
var lcp = LcpArray(s, sa);
var flg = false;
var mlcp = int.MaxValue;
var ans = s.Length - 1;
for (var i = sa.Length - 1; i >= 0; --i)
{
if (sa[i] == 0)
{
flg = true;
}
else if (flg)
{
mlcp = Math.Min(mlcp, lcp[i]);
if (mlcp < sa[i]) --ans;
else if (sa[i] * 2 == s.Length) --ans;
// --ans;
}
}
return ans;
}
// s.Substring(i) を辞書順でソートしたときの i のリストを返却する
// O(n)
static int[] SuffixArray(string s)
{
var n = s.Length;
var s2 = new int[n];
for (var i = 0; i < n; ++i) s2[i] = (int)s[i];
return SaIs(s2, 255);
}
// 文字列 s の Suffix Array を並べたとき隣接する項目の Longest Common Path を求める
static int[] LcpArray(string s, int[] sa)
{
var n = s.Length;
var s2 = new int[n];
for (var i = 0; i < n; ++i) s2[i] = (int)s[i];
return LcpArray(s2, sa);
}
static int[] LcpArray(int[] s, int[] sa)
{
var n = s.Length;
var rnk = new int[n];
for (var i = 0; i < n; ++i) rnk[sa[i]] = i;
var lcp = new int[n - 1];
var h = 0;
for (var i = 0; i < n; ++i)
{
if (h > 0) --h;
if (rnk[i] == 0) continue;
var j = sa[rnk[i] - 1];
for (; j + h < n && i + h < n; ++h)
{
if (s[j + h] != s[i + h]) break;
}
lcp[rnk[i] - 1] = h;
}
return lcp;
}
static int[] SaNaive(int[] s)
{
var n = s.Length;
var sa = new List<int>(n);
for (var i = 0; i < n; ++i)
{
sa.Add(i);
}
sa.Sort((l, r) => {
if (l == r) return 1;
while (l < n && r < n)
{
if (s[l] != s[r]) return s[l] < s[r] ? -1 : 1;
++l;
++r;
}
return l == n ? -1 : 1;
});
return sa.ToArray();
}
static int[] SaDoubling(int[] s)
{
var n = s.Length;
var sa = new List<int>(n);
var rnk = s;
var tmp = new int[n];
for (var i = 0; i < n; ++i) sa.Add(i);
for (var k = 1; k < n; k *= 2)
{
Comparison<int> cmp = (x, y) =>
{
if (rnk[x] != rnk[y]) return rnk[x] < rnk[y] ? -1 : 1;
var rx = x + k < n ? rnk[x + k] : -1;
var ry = y + k < n ? rnk[y + k] : -1;
return rx < ry ? -1 : 1;
};
sa.Sort(cmp);
tmp[sa[0]] = 0;
for (var i = 1; i < n; ++i) tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) == -1 ? 1 : 0);
var tmp2 = tmp;
tmp = rnk;
rnk = tmp2;
}
return sa.ToArray();
}
const int THRESHOLD_NAIVE = 10;
const int THRESHOLD_DOUBLING = 40;
static int[] SaIs(int[] s, int upper)
{
var n = s.Length;
if (n == 0) return new int[0];
if (n == 1) return new int[] { 0 };
if (n == 2)
{
if (s[0] < s[1]) return new int[] { 0, 1 };
else return new int[] { 1, 0 };
}
if (n < THRESHOLD_NAIVE) return SaNaive(s);
if (n < THRESHOLD_DOUBLING) return SaDoubling(s);
var sa = new int[n];
var ls = new bool[n];
for (var i = n - 2; i >= 0; --i) ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
var sumL = new int[upper + 1];
var sumS = new int[upper + 1];
for (var i = 0; i < n; ++i)
{
if (!ls[i]) ++sumS[s[i]];
else ++sumL[s[i] + 1];
}
for (var i = 0; i <= upper; ++i)
{
sumS[i] += sumL[i];
if (i < upper) sumL[i + 1] += sumS[i];
}
Func<List<int>, int> induce = (List<int> _lms) =>
{
for (var i = 0; i < sa.Length; ++i) sa[i] = -1;
var buf = new int[upper + 1];
Array.Copy(sumS, buf, sumS.Length);
foreach (var d in _lms)
{
if (d == n) continue;
sa[buf[s[d]]++] = d;
}
Array.Copy(sumL, buf, sumL.Length);
sa[buf[s[n - 1]]++] = n - 1;
for (var i = 0; i < n; ++i)
{
var v = sa[i];
if (v >= 1 && !ls[v - 1]) sa[buf[s[v - 1]]++] = v - 1;
}
Array.Copy(sumL, buf, sumL.Length);
for (var i = n - 1; i >= 0; --i)
{
var v = sa[i];
if (v >= 1 && ls[v - 1]) sa[--buf[s[v - 1] + 1]] = v - 1;
}
return 0;
};
var lmsMap = new int[n + 1];
for (var i = 0; i < lmsMap.Length; ++i) lmsMap[i] = -1;
var m = 0;
for (var i = 1; i < n; ++i)
{
if (!ls[i - 1] && ls[i]) lmsMap[i] = m++;
}
var lms = new List<int>(m);
for (var i = 1; i < n; ++i)
{
if (!ls[i - 1] && ls[i]) lms.Add(i);
}
induce(lms);
if (m > 0)
{
var sortedLms = new List<int>(m);
foreach (var v in sa)
{
if (lmsMap[v] != -1) sortedLms.Add(v);
}
var recS = new int[m];
var recUpper = 0;
recS[lmsMap[sortedLms[0]]] = 0;
for (var i = 1; i < m; ++i)
{
var l = sortedLms[i - 1];
var r = sortedLms[i];
var endL = (lmsMap[l] + 1 < m) ? lms[lmsMap[l] + 1] : n;
var endR = (lmsMap[r] + 1 < m) ? lms[lmsMap[r] + 1] : n;
var same = true;
if (endL - l != endR - r) same = false;
else
{
while (l < endL)
{
if (s[l] != s[r]) break;
++l;
++r;
}
same = (l != n && s[l] == s[r]);
}
if (!same) ++recUpper;
recS[lmsMap[sortedLms[i]]] = recUpper;
}
var recSa = SaIs(recS, recUpper);
for (var i = 0; i < m; ++i) sortedLms[i] = lms[recSa[i]];
induce(sortedLms);
}
return sa;
}
}