結果
問題 | No.464 PPAP |
ユーザー |
|
提出日時 | 2016-12-09 19:19:02 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 231 ms / 2,000 ms |
コード長 | 2,012 bytes |
コンパイル時間 | 6,288 ms |
コンパイル使用メモリ | 79,292 KB |
実行使用メモリ | 41,708 KB |
最終ジャッジ日時 | 2024-11-28 19:37:27 |
合計ジャッジ時間 | 11,112 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 22 |
ソースコード
import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; public class N464 { static Scanner in; static PrintWriter out; static String INPUT = ""; static void solve() { char[] s = in.next().toCharArray(); if(!(s.length >= 4))throw new AssertionError(); if(!(s.length <= 5000))throw new AssertionError(); for(char c : s){ if(!(c >= 'a' && c <= 'z'))throw new AssertionError(); } int n = s.length; int[] rads = palindrome(s); int[] p1p2 = new int[n]; for(int i = 0;i < 2*n;i++){ // center of P1 if(rads[i] > 0 && i-(rads[i]-1) == 0){ // if prefix int sp2 = i+rads[i]+1; for(int j = i+rads[i]+1;j < 2*n;j++){ // center of P2 if(rads[j] > 0 && j-(rads[j]-1) <= sp2){ p1p2[(2*j-sp2)/2]++; } } } } for(int i = 1;i < n;i++){ p1p2[i] += p1p2[i-1]; } long ret = 0; for(int i = 0;i < 2*n;i++){ // center of P3 if(rads[i] > 0 && i+(rads[i]-1) == 2*n-2){ // if suffix if((i-(rads[i]-1))/2-2 >= 0){ ret += (long)p1p2[(i-(rads[i]-1))/2-2]; } } } out.println(ret); } public static int[] palindrome(char[] str) { int n = str.length; int[] r = new int[2*n]; int k = 0; for(int i = 0, j = 0;i < 2*n;i += k, j = Math.max(j-k, 0)){ // normally while(i-j >= 0 && i+j+1 < 2*n && str[(i-j)/2] == str[(i+j+1)/2])j++; r[i] = j; // skip based on the theorem for(k = 1;i-k >= 0 && r[i]-k >= 0 && r[i-k] != r[i]-k;k++){ r[i+k] = Math.min(r[i-k], r[i]-k); } } return r; } public static void main(String[] args) throws Exception { in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT); out = new PrintWriter(System.out); solve(); out.flush(); } static int ni() { return Integer.parseInt(in.next()); } static long nl() { return Long.parseLong(in.next()); } static double nd() { return Double.parseDouble(in.next()); } static void tr(Object... o) { if (INPUT.length() != 0) System.out.println(Arrays.deepToString(o)); } }