結果

問題 No.2454 Former < Latter
ユーザー 👑 kakel-sankakel-san
提出日時 2023-09-01 23:13:08
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 170 ms / 2,000 ms
コード長 7,410 bytes
コンパイル時間 1,352 ms
コンパイル使用メモリ 68,780 KB
実行使用メモリ 33,656 KB
最終ジャッジ日時 2023-09-01 23:13:15
合計ジャッジ時間 5,677 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 59 ms
18,680 KB
testcase_01 AC 60 ms
22,824 KB
testcase_02 AC 94 ms
28,744 KB
testcase_03 AC 88 ms
30,704 KB
testcase_04 AC 113 ms
31,472 KB
testcase_05 AC 112 ms
32,940 KB
testcase_06 AC 117 ms
31,724 KB
testcase_07 AC 114 ms
30,264 KB
testcase_08 AC 130 ms
26,928 KB
testcase_09 AC 110 ms
31,036 KB
testcase_10 AC 118 ms
31,224 KB
testcase_11 AC 87 ms
28,688 KB
testcase_12 AC 94 ms
30,668 KB
testcase_13 AC 86 ms
26,584 KB
testcase_14 AC 86 ms
28,656 KB
testcase_15 AC 144 ms
33,088 KB
testcase_16 AC 144 ms
33,656 KB
testcase_17 AC 170 ms
28,348 KB
testcase_18 AC 157 ms
26,960 KB
testcase_19 AC 152 ms
33,336 KB
testcase_20 AC 144 ms
31,372 KB
testcase_21 AC 134 ms
26,896 KB
testcase_22 AC 115 ms
30,400 KB
testcase_23 AC 118 ms
26,328 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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;
    }

}
0