結果

問題 No.2454 Former < Latter
ユーザー ks2mks2m
提出日時 2023-09-01 23:57:35
言語 Java21
(openjdk 21)
結果
AC  
実行時間 276 ms / 2,000 ms
コード長 7,909 bytes
コンパイル時間 3,591 ms
コンパイル使用メモリ 90,096 KB
実行使用メモリ 55,940 KB
最終ジャッジ日時 2024-06-11 06:16:22
合計ジャッジ時間 8,287 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 52 ms
50,316 KB
testcase_01 AC 52 ms
50,172 KB
testcase_02 AC 117 ms
54,404 KB
testcase_03 AC 108 ms
53,968 KB
testcase_04 AC 103 ms
54,140 KB
testcase_05 AC 113 ms
54,068 KB
testcase_06 AC 123 ms
53,892 KB
testcase_07 AC 118 ms
54,052 KB
testcase_08 AC 128 ms
54,772 KB
testcase_09 AC 108 ms
53,704 KB
testcase_10 AC 104 ms
53,876 KB
testcase_11 AC 111 ms
53,944 KB
testcase_12 AC 110 ms
53,772 KB
testcase_13 AC 102 ms
53,984 KB
testcase_14 AC 110 ms
53,844 KB
testcase_15 AC 119 ms
53,792 KB
testcase_16 AC 112 ms
53,804 KB
testcase_17 AC 276 ms
55,940 KB
testcase_18 AC 138 ms
54,772 KB
testcase_19 AC 120 ms
54,192 KB
testcase_20 AC 127 ms
53,964 KB
testcase_21 AC 137 ms
54,400 KB
testcase_22 AC 110 ms
53,636 KB
testcase_23 AC 102 ms
54,296 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.function.Consumer;
import java.util.function.IntBinaryOperator;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		PrintWriter pw = new PrintWriter(System.out);
		for (int z = 0; z < t; z++) {
			int n = Integer.parseInt(br.readLine());
			char[] s = br.readLine().toCharArray();

			//* char[] s2 = "ababac".toCharArray();
			//* int[] za = StringAC.zAlgorithm(s2);  // [6, 0, 3, 0, 1, 0]
			int[] za = StringAC.zAlgorithm(s);
			int ans = 0;
			for (int i = 1; i < n; i++) {
				if (za[i] > i ||
						za[i] == i && i < n - i ||
						i + za[i] < n && s[za[i]] < s[i + za[i]]) {
					ans++;
				}
			}
			pw.println(ans);
		}
		pw.flush();
		br.close();
	}
}

class StringAC {
	private static final int THRESHOLD_NAIVE = 50;

	/**
	 * 長さnの文字配列sのSuffix Arrayとして、長さnの配列を返す。<br>
	 * 戻り値の配列は、x＝0～(n-1)の順列で、「s[x]..s[n-1]」の昇順。<br>
	 * O(n)
	 */
	static int[] suffixArray(char[] s) {
		int n = s.length;
		int[] s2 = new int[n];
		for (int i = 0; i < n; i++) {
			s2[i] = s[i];
		}
		return sais(s2, 255);
	}

	/**
	 * 長さnの数値配列sのSuffix Arrayとして、長さnの配列を返す。<br>
	 * 戻り値の配列は、x＝0～(n-1)の順列で、「s[x]..s[n-1]」の昇順。<br>
	 * 時間：O(n log n)、空間：O(n)
	 */
	static int[] suffixArray(int[] s) {
		int n = s.length;
		int[] vals = Arrays.copyOf(s, n);
		Arrays.sort(vals);
		int p = 1;
		for (int i = 1; i < n; i++) {
			if (vals[i] != vals[i - 1]) {
				vals[p++] = vals[i];
			}
		}
		int[] s2 = new int[n];
		for (int i = 0; i < n; i++) {
			s2[i] = Arrays.binarySearch(vals, 0, p, s[i]);
		}
		return sais(s2, p);
	}

	/**
	 * 長さnの数値配列sのSuffix Arrayとして、長さnの配列を返す。<br>
	 * 戻り値の配列は、x＝0～(n-1)の順列で、「s[x]..s[n-1]」の昇順。<br>
	 * 0≦sの全要素≦upper<br>
	 * O(n + upper)
	 */
	static int[] suffixArray(int[] s, int upper) {
		assert (0 <= upper);
		for (int d : s) {
			assert (0 <= d && d <= upper) : "d=" + d + ", upper=" + upper;
		}
		return sais(s, upper);
	}

	/**
	 * 長さnの文字配列sのLCP Arrayとして、長さn-1の配列を返す。<br>
	 * 戻り値の配列のi番目は、sa[i]と[i+1]の共通接頭辞の長さ。<br>
	 * O(n)
	 * 
	 * @param s 元の文字配列
	 * @param sa Suffix Array
	 */
	static int[] lcpArray(char[] s, int[] sa) {
		int n = s.length;
		int[] s2 = new int[n];
		for (int i = 0; i < n; i++) {
			s2[i] = s[i];
		}
		return lcpArray(s2, sa);
	}

	/**
	 * 長さnの数値配列sのLCP Arrayとして、長さn-1の配列を返す。<br>
	 * 戻り値の配列のi番目は、sa[i]と[i+1]の共通接頭辞の長さ。<br>
	 * O(n)
	 * 
	 * @param s 元の数値配列
	 * @param sa Suffix Array
	 */
	static int[] lcpArray(int[] s, int[] sa) {
		int n = s.length;
		assert (n >= 1);
		int[] rnk = new int[n];
		for (int i = 0; i < n; i++) {
			rnk[sa[i]] = i;
		}
		int[] lcp = new int[n - 1];
		int h = 0;
		for (int i = 0; i < n; i++) {
			if (h > 0) h--;
			if (rnk[i] == 0) {
				continue;
			}
			int 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;
	}

	/**
	 * 入力の長さをnとして、長さnの配列を返す。<br>
	 * 戻り値の配列のi番目は、「s[0]..s[n-1]」と「s[i]..s[n-1]」の共通接頭辞の長さ。<br>
	 * O(n)
	 */
	static int[] zAlgorithm(char[] s) {
		int n = s.length;
		if (n == 0) return new int[0];
		int[] z = new int[n];
		for (int i = 1, j = 0; i < n; i++) {
			int k = j + z[j] <= i ? 0 : Math.min(j + z[j] - i, z[i - j]);
			while (i + k < n && s[k] == s[i + k]) k++;
			z[i] = k;
			if (j + z[j] < i + z[i]) j = i;
		}
		z[0] = n;
		return z;
	}

	/**
	 * 入力の長さをnとして、長さnの配列を返す。<br>
	 * 戻り値の配列のi番目は、「s[0]..s[n-1]」と「s[i]..s[n-1]」の共通接頭辞の長さ。<br>
	 * O(n)
	 */
	int[] zAlgorithm(int[] s) {
		int n = s.length;
		if (n == 0) return new int[0];
		int[] z = new int[n];
		for (int i = 1, j = 0; i < n; i++) {
			int k = j + z[j] <= i ? 0 : Math.min(j + z[j] - i, z[i - j]);
			while (i + k < n && s[k] == s[i + k]) k++;
			z[i] = k;
			if (j + z[j] < i + z[i]) j = i;
		}
		z[0] = n;
		return z;
	}

	private static int[] sais(int[] s, int upper) {
		int 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);
		}

		int[] sa = new int[n];
		boolean[] ls = new boolean[n];
		for (int i = n - 2; i >= 0; i--) {
			ls[i] = s[i] == s[i + 1] ? ls[i + 1] : s[i] < s[i + 1];
		}

		int[] sumL = new int[upper + 1];
		int[] sumS = new int[upper + 1];

		for (int i = 0; i < n; i++) {
			if (ls[i]) {
				sumL[s[i] + 1]++;
			} else {
				sumS[s[i]]++;
			}
		}

		for (int i = 0; i <= upper; i++) {
			sumS[i] += sumL[i];
			if (i < upper) sumL[i + 1] += sumS[i];
		}

		Consumer<int[]> induce = lms -> {
			Arrays.fill(sa, -1);
			int[] buf = new int[upper + 1];
			System.arraycopy(sumS, 0, buf, 0, upper + 1);
			for (int d : lms) {
				if (d == n) continue;
				sa[buf[s[d]]++] = d;
			}
			System.arraycopy(sumL, 0, buf, 0, upper + 1);
			sa[buf[s[n - 1]]++] = n - 1;
			for (int i = 0; i < n; i++) {
				int v = sa[i];
				if (v >= 1 && !ls[v - 1]) {
					sa[buf[s[v - 1]]++] = v - 1;
				}
			}
			System.arraycopy(sumL, 0, buf, 0, upper + 1);
			for (int i = n - 1; i >= 0; i--) {
				int v = sa[i];
				if (v >= 1 && ls[v - 1]) {
					sa[--buf[s[v - 1] + 1]] = v - 1;
				}
			}
		};

		int[] lmsMap = new int[n + 1];
		Arrays.fill(lmsMap, -1);
		int m = 0;
		for (int i = 1; i < n; i++) {
			if (!ls[i - 1] && ls[i]) {
				lmsMap[i] = m++;
			}
		}

		int[] lms = new int[m];
		{
			int p = 0;
			for (int i = 1; i < n; i++) {
				if (!ls[i - 1] && ls[i]) {
					lms[p++] = i;
				}
			}
		}

		induce.accept(lms);

		if (m > 0) {
			int[] sortedLms = new int[m];
			{
				int p = 0;
				for (int v : sa) {
					if (lmsMap[v] != -1) {
						sortedLms[p++] = v;
					}
				}
			}
			int[] recS = new int[m];
			int recUpper = 0;
			recS[lmsMap[sortedLms[0]]] = 0;
			for (int i = 1; i < m; i++) {
				int l = sortedLms[i - 1], r = sortedLms[i];
				int endL = (lmsMap[l] + 1 < m) ? lms[lmsMap[l] + 1] : n;
				int endR = (lmsMap[r] + 1 < m) ? lms[lmsMap[r] + 1] : n;
				boolean same = true;
				if (endL - l != endR - r) {
					same = false;
				} else {
					while (l < endL && s[l] == s[r]) {
						l++;
						r++;
					}
					if (l == n || s[l] != s[r]) same = false;
				}
				if (!same) {
					recUpper++;
				}
				recS[lmsMap[sortedLms[i]]] = recUpper;
			}

			int[] recSA = sais(recS, recUpper);

			for (int i = 0; i < m; i++) {
				sortedLms[i] = lms[recSA[i]];
			}
			induce.accept(sortedLms);
		}
		return sa;
	}

	private static int[] saNaive(int[] s) {
		int n = s.length;
		int[] sa = new int[n];
		for (int i = 0; i < n; i++) {
			sa[i] = i;
		}
		insertionsort(sa, (l, r) -> {
			while (l < n && r < n) {
				if (s[l] != s[r]) return s[l] - s[r];
				l++;
				r++;
			}
			return -(l - r);
		});
		return sa;
	}

	private static void insertionsort(int[] a, IntBinaryOperator comparator) {
		final int n = a.length;
		for (int i = 1; i < n; i++) {
			final int tmp = a[i];
			if (comparator.applyAsInt(a[i - 1], tmp) > 0) {
				int j = i;
				do {
					a[j] = a[j - 1];
					j--;
				} while (j > 0 && comparator.applyAsInt(a[j - 1], tmp) > 0);
				a[j] = tmp;
			}
		}
	}
}
0