結果
| 問題 | No.1018 suffixsuffixsuffix |
| コンテスト | |
| ユーザー |
 kakel-san
|
| 提出日時 | 2025-11-20 23:17:59 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 205 ms / 2,000 ms |
| コード長 | 13,380 bytes |
| コンパイル時間 | 8,849 ms |
| コンパイル使用メモリ | 170,572 KB |
| 実行使用メモリ | 225,448 KB |
| 最終ジャッジ日時 | 2025-11-20 23:18:26 |
| 合計ジャッジ時間 | 19,072 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 34 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (127 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Runtime.CompilerServices;
using System.Runtime.Intrinsics.X86;
class Program
{
static int NN => int.Parse(ReadLine());
static long[] NList => ReadLine().Split().Select(long.Parse).ToArray();
public static void Main()
{
Solve();
}
static void Solve()
{
var c = NList;
var (n, m, q) = ((int)c[0], (int)c[1], (int)c[2]);
var s = ReadLine();
var k = NList;
WriteLine(string.Join(" ", Suffix(n, m, q, s, k)));
}
static long[] Suffix(int n, long m, int q, string s, long[] k)
{
var h1 = new StringHash(SHI.H1, s);
var h2 = new StringHash(SHI.H2, s);
for (var i = 1; i < n; ++i)
{
if (n % i == 0)
{
var sh1 = h1.GetHash(0, i - 1);
var sh2 = h2.GetHash(0, i - 1);
var flg = true;
for (var j = i; j < n; j += i)
{
var nsh1 = h1.GetHash(j, j + i - 1);
var nsh2 = h2.GetHash(j, j + i - 1);
if (sh1 != nsh1 || sh2 != nsh2)
{
flg = false;
break;
}
}
if (flg)
{
s = s[0..i];
m *= n / i;
n = i;
break;
}
}
}
return SuffixImpl(n, m, q, s, k);
}
static long[] SuffixImpl(int n, long m, int q, string s, long[] k)
{
var t = s + s;
var sa = SuffixArray(t);
var list = new List<(int pos, long min, long max)>(sa.Length);
var offset = 1L;
for (var i = 0; i < sa.Length; ++i)
{
if (sa[i] >= n)
{
list.Add((sa[i], offset, offset));
++offset;
}
else
{
list.Add((sa[i], offset, offset + m - 2));
offset += m - 1;
}
}
var qlist = new List<(int id, long k)>(q);
for (var i = 0; i < q; ++i) qlist.Add((i, k[i]));
qlist.Sort((l, r) => l.k.CompareTo(r.k));
var ans = new long[q];
var pos = 0;
foreach (var qi in qlist)
{
while (list[pos].max < qi.k) ++pos;
if (list[pos].pos >= n)
{
ans[qi.id] = list[pos].pos + (m - 2L) * n + 1;
}
else
{
ans[qi.id] = list[pos].pos + (list[pos].max - qi.k) * n + 1;
}
}
return ans;
}
public class SHI
{
public static SHI H1 = new SHI(29, 998_244_391, 722_866_628);
public static SHI H2 = new SHI(31, 998_244_397, 193_208_593);
public int Mul;
public int Mod;
public int Rev;
public SHI(int mul, int mod, int rev)
{
Mul = mul; Mod = mod; Rev = rev;
}
}
/// 部分文字列に対するハッシュコードを計算する
class StringHash
{
int mul;
int mod;
long[] pow;
long[] rev;
// ここをFenwicktree等に変更することで、文字列の変更ができる
long[] cum;
// FenwickTree cum;
public StringHash(SHI ini, string s)
{
mul = ini.Mul;
mod = ini.Mod;
pow = new long[s.Length + 1];
rev = new long[s.Length + 1];
pow[0] = 1;
rev[0] = 1;
cum = new long[s.Length + 1];
// cum = new FenwickTree(s.Length + 1);
for (var i = 1; i <= s.Length; ++i)
{
pow[i] = pow[i - 1] * mul % mod;
rev[i] = rev[i - 1] * ini.Rev % mod;
cum[i] = (cum[i - 1] + (s[i - 1] - 'a' + 1) * pow[i]) % mod;
// cum.Add(i, (s[i - 1] - 'a' + 1) * pow[i] % mod);
}
}
/// <summary>部分文字列s[l..r]のハッシュ1を求める l,rは0-based</summary>
public int GetHash(int l, int r)
{
if (l > r) return 0;
return (int)((cum[r + 1] + mod - cum[l]) % mod * rev[l] % mod);
}
// public int GetHash(int l, int r)
// {
// if (l > r) return 0;
// return (int)((cum.Sum(r + 1) - cum.Sum(l) + mod) % mod * rev[l] % mod);
// }
}
// 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);
}
// 時間 O(nlogn), 空間 O(n)
static int[] SuffixArray(int[] s)
{
var n = s.Length;
var idx = new List<int>(n);
for (var i = 0; i < n; ++i) idx.Add(i);
idx.Sort((l, r) => s[l].CompareTo(s[r]));
var s2 = new int[n];
var now = 0;
for (var i = 0; i < n; ++i)
{
if (i > 0 && s[idx[i - 1]] != s[idx[i]]) ++now;
s2[idx[i]] = now;
}
return SaIs(s2, now);
}
// sに含まれる値が 0 から upper までの間に限られる場合
// O(n + upper)
static int[] SuffixArray(int[] s, int upper)
{
return SaIs(s, upper);
}
// 文字列 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;
}
// s と s.Substring(i) の Longest Common Prefix の長さを格納した配列を取得する
static int[] ZAlgorithm(string s)
{
var n = s.Length;
var s2 = new int[n];
for (var i = 0; i < n; ++i) s2[i] = (int)s[i];
return ZAlgorithm(s2);
}
static int[] ZAlgorithm(int[] s)
{
var n = s.Length;
if (n == 0) return new int[] {};
var z = new int[n];
for (int i = 1, j = 0; i < n; ++i)
{
z[i] = (j + z[j] <= i) ? 0 : Math.Min(j + z[j] - i, z[i - j]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
if (j + z[j] < i + z[i]) j = i;
}
z[0] = n;
return z;
}
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;
}
// クヌース-モリス-プラット法
static int[] InitKmp<T>(T[] w) where T : IEquatable<T>
{
var result = new int[w.Length];
result[0] = -1;
if (w.Length > 1) result[1] = 0;
var pos = 0;
for (var i = 1; i < result.Length - 1; ++i)
{
if (w[pos].Equals(w[i])) ++pos;
else pos = 0;
result[i + 1] = pos;
}
return result;
}
static int KMPSearch<T>(T[] s, T[] w, int start, int[] subTable) where T : IEquatable<T>
{
var m = start;
var i = 0;
while (m + i < s.Length)
{
if (s[m + i].Equals(w[i]))
{
++i;
if (i == w.Length) return m;
}
else
{
++m;
if (i > 0)
{
m += i - subTable[i];
i = subTable[i];
}
}
}
return -1;
}
}