#137088 (Java) No.464 PPAP

• 問題: No.464 PPAP
• ユーザー: uwi
• 提出日時: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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));
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX