#990643 (C++17) No.2454 Former < Latter

提出ソース

結果

問題	No.2454 Former < Latter
ユーザー	tnakao0123
提出日時	2024-06-24 16:14:25
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,548 bytes
コンパイル時間	943 ms
コンパイル使用メモリ	75,396 KB
実行使用メモリ	12,416 KB
最終ジャッジ日時	2024-06-24 16:14:34
合計ジャッジ時間	2,964 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	WA	-
testcase_02	AC	22 ms 9,216 KB
testcase_03	AC	22 ms 9,344 KB
testcase_04	AC	27 ms 9,344 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	23 ms 6,940 KB
testcase_10	AC	28 ms 6,940 KB
testcase_11	AC	21 ms 9,344 KB
testcase_12	WA	-
testcase_13	AC	23 ms 9,216 KB
testcase_14	AC	23 ms 9,344 KB
testcase_15	WA	-
testcase_16	AC	34 ms 6,940 KB
testcase_17	AC	404 ms 12,416 KB
testcase_18	WA	-
testcase_19	AC	38 ms 9,328 KB
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	28 ms 6,944 KB
testcase_23	AC	27 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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