Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
SubmitStatusPracticeHDU 3068
Description
a,b,c…y,zS,S.
,aba, abba

Input
case,120,a,b,c…y,zS
case()
len

Output
x,case,case.

Sample Input
aaaa

abab

Sample Output
4
3

?Download sourceCode.cpp
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

#include <iostream>
#include <cstdio>
#include <cstring>
 
using namespace std;
 
#define N 110005
char str[N];
char strf[2 * N];
int rad[2 * N];
int len;
 
void init(){
    int i, j;
    len = strlen(str);
    strf[0] = '@';
    strf[1] = '#';
    for(i = 0; i < len; i ++){
        strf[i * 2 + 2] = str[i];
        strf[i * 2 + 3] = '#';
    }
    strf[len * 2 + 2] = '$';
    len = len * 2 + 3;
}
 
int main(){
    while(~scanf("%s", str)){
        init();
        //cout << strf << endl;
        memset(rad, 0, sizeof(rad));
        int mx = 0, id;
        int len = strlen(strf);
        for(int i = 1; i < len - 1; i++){
            if(mx > i)
                rad[i] = min(rad[2 * id - i], rad[id] + id - i);
            else
                rad[i] = 1;
            while(strf[i + rad[i]] == strf[i - rad[i]])
                rad[i]++;
            if(rad[i] + i > mx){
                mx = rad[i] + i;
                id = i;
            }
        }
        int ans = 0;
        for(int i = 0; i < len; i ++){
            //printf("%d\n", rad[i]);
            if(rad[i] > ans)
                ans = rad[i];
        }
        printf("%d\n", ans - 1);
    }
    return 0;
}

manacherans

?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10

        for(int i = 1, j = 0, k; i < len;){
            while(strf[i - j - 1] == strf[i + j + 1])
                j ++;
            rad[i] = j;
            for(k = 1; k <= j && rad[i - k] != rad[i] - k; k ++){
                rad[i + k] = min(rad[i - k], rad[i] - k);
            }
            i += k;
            j = max(j - k, 0);
        }