結果
| 問題 |
No.2454 Former < Latter
|
| コンテスト | |
| ユーザー |
 tnakao0123
|
| 提出日時 | 2024-06-24 16:14:25 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,548 bytes |
| コンパイル時間 | 943 ms |
| コンパイル使用メモリ | 74,948 KB |
| 最終ジャッジ日時 | 2025-02-22 00:18:45 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 13 WA * 10 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:222:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
222 | scanf("%d", &tn);
| ~~~~~^~~~~~~~~~~
main.cpp:226:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
226 | scanf("%d%s", &n, s);
| ~~~~~^~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*-
*
* 2454.cc: No.2454 Former < Latter - yukicoder
*/
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
/* constant */
const int MAX_N = 300000;
/* typedef */
using vi = vector<int>;
using uchar = unsigned char;
using vuc = vector<uchar>;
/* global variables */
char s[MAX_N + 4];
/* subroutines */
inline uchar mask(int i) { return (uchar)(1 << (7 - i)); }
inline bool tget(vuc &t, int i) {
return (t[i / 8] & mask(i % 8)) ? true : false;
}
inline void tset(vuc &t, int i, bool b) {
if (b) t[i / 8] |= mask(i % 8);
else t[i / 8] &= ~mask(i % 8);
}
inline bool isLMS(vuc &t, int i) {
return (i > 0 && tget(t, i) && ! tget(t, i - 1));
}
// find the start or end of each bucket
void getBuckets(int *s, vi &bkt, int n, int k, bool end) {
// clear all buckets
bkt.assign(k, 0);
// compute the size of each bucket
for (int i = 0; i < n; i++) bkt[s[i]]++;
for (int i = 0, sum = 0; i < k; i++) {
sum += bkt[i];
bkt[i] = end ? sum : sum - bkt[i];
}
}
// compute SAl
void induceSAl(vuc &t, int *SA, int *s, vi &bkt, int n, int k, bool end) {
// find starts of buckets
getBuckets(s, bkt, n, k, end);
for (int i = 0; i < n; i++) {
int j = SA[i] - 1;
if (j >= 0 && ! tget(t, j)) SA[bkt[s[j]]++] = j;
}
}
// compute SAs
void induceSAs(vuc &t, int *SA, int *s, vi &bkt, int n, int k, bool end) {
// find ends of buckets
getBuckets(s, bkt, n, k, end);
for (int i = n - 1; i >= 0; i--) {
int j = SA[i] - 1;
if (j >= 0 && tget(t, j)) SA[--bkt[s[j]]] = j;
}
}
// find the suffix array SA of s[0..n-1] in {1..K}
// require s[n-1]=0 (the sentinel!), n>=2
// use a working space (excluding s and SA) of
// at most 2.25n+O(1) for a constant alphabet
void SA_IS(int *s, int *SA, int n, int k) {
// LS-type array in bits
vuc t(n / 8 + 1);
// classify the type of each character
// the sentinel must be in s1, important!!!
tset(t, n - 1, true);
tset(t, n - 2, false);
for (int i = n - 3; i >= 0; i--)
if (s[i] < s[i + 1] || (s[i] == s[i + 1] && tget(t, i + 1)))
tset(t, i, true);
// stage 1: reduce the problem by at least 1/2
// sort all the S-substrings
// bucket array
vi bkt(k);
// find ends of buckets
getBuckets(s, bkt, n, k, true);
for (int i = 0; i < n; i++) SA[i] = -1;
for (int i = 1; i < n; i++)
if (isLMS(t, i)) SA[--bkt[s[i]]] = i;
induceSAl(t, SA, s, bkt, n, k, false);
induceSAs(t, SA, s, bkt, n, k, true);
// compact all the sorted substrings into
// the first n1 items of SA
// 2*n1 must be not larger than n (proveable)
int n1 = 0;
for (int i = 0; i < n; i++)
if (isLMS(t, SA[i])) SA[n1++] = SA[i];
// find the lexicographic names of substrings
// init the name array buffer
for (int i = n1; i < n; i++) SA[i] = -1;
int name = 0, prev = -1;
for (int i = 0; i < n1; i++) {
int pos = SA[i];
bool diff = false;
for (int d = 0; d < n; d++) {
if (prev == -1 || s[pos + d] != s[prev + d] ||
tget(t, pos + d) != tget(t, prev + d)) {
diff = true;
break;
}
else if (d > 0 && (isLMS(t, pos + d) || isLMS(t, prev + d)))
break;
}
if (diff) name++, prev = pos;
pos /= 2;
SA[n1 + pos] = name - 1;
}
for (int i = n - 1, j = n - 1; i >= n1; i--)
if (SA[i] >= 0) SA[j--] = SA[i];
// stage 2: solve the reduced problem
// recurse if names are not yet unique
int *SA1 = SA, *s1 = SA + n - n1;
if (name < n1)
SA_IS(s1, SA1, n1, name);
else // generate the suffix array of s1 directly
for (int i = 0; i < n1; i++) SA1[s1[i]] = i;
// stage 3: induce the result for
// the original problem
// bucket array
bkt.assign(k, 0);
// put all the LMS characters into their buckets
// find ends of buckets
getBuckets(s, bkt, n, k, true);
for (int i = 1, j = 0; i < n; i++)
if (isLMS(t, i)) s1[j++] = i; // get p1
// get index in s
for (int i = 0; i < n1; i++) SA1[i] = s1[SA1[i]];
// init SA[n1..n-1]
for (int i = n1; i < n; i++) SA[i] = -1;
for (int i = n1 - 1; i >= 0; i--) {
int j=SA[i];
SA[i] = -1;
SA[--bkt[s[j]]] = j;
}
induceSAl(t, SA, s, bkt, n, k, false);
induceSAs(t, SA, s, bkt, n, k, true);
}
void SA_IS(string &s, vi &SA, int k = 256) {
int n = s.size();
int *buf0 = new int[n + 1], *buf1 = new int[n + 1];
for (int i = 0; i < n; i++) buf0[i] = s[i];
buf0[n] = 0;
SA_IS(buf0, buf1, n + 1, k);
SA.resize(n + 1);
for (int i = 0; i <= n; i++) SA[i] = buf1[i];
}
void LCP(string &s, vi &sa, vi &lcp) {
int n = s.size();
lcp.resize(n + 1);
vi rank_(n + 1);
for (int i = 0; i <= n; i++) rank_[sa[i]] = i;
int h = 0;
lcp[0] = 0;
for (int i = 0; i < n; i++) {
int j = sa[rank_[i] - 1];
if (h > 0) h--;
for (; j + h < n && i + h < n; h++)
if (s[j + h] != s[i + h]) break;
lcp[rank_[i]] = h;
}
}
/*
int main() {
string s("abracadabra");
vi SA, lcp;
SA_IS(s, SA);
LCP(s, SA, lcp);
for (int i = 0; i < SA.size(); i++)
printf("%d %d\n", SA[i], lcp[i]);
}
*/
/* main */
int main() {
int tn;
scanf("%d", &tn);
while (tn--) {
int n;
scanf("%d%s", &n, s);
string t(s);
vi sa, lcp;
SA_IS(t, sa);
LCP(t, sa, lcp);
//puts(s);
//for (int i = 0; i < sa.size(); i++)
// printf("%d %d\n", sa[i], lcp[i]);
int x = 0;
for (; x < sa.size() && sa[x] != 0; x++);
//printf(" x=%d\n", x);
int c = n - x;
while (x > 0 && sa[x - 1] < lcp[x]) c++, x--;
printf("%d\n", c);
}
return 0;
}