-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmancher.cpp
More file actions
114 lines (99 loc) · 2.44 KB
/
mancher.cpp
File metadata and controls
114 lines (99 loc) · 2.44 KB
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char s[1000];
char s_new[2000];
int p[2000];
int mancher();
int main(){
int len;
len=mancher();
cout<<len<<endl;
return 0;
}
int mancher(){
cin>>s;
int len=strlen(s);
int id;
int mx=0;
int max_len=-1;
s_new[0]='$';
s_new[1]='#';
int j=2;
for(int i=0;i<len;i++){
s_new[j++]=s[i];
s_new[j++]='#';
}
s_new[j++]='^';
s_new[j]='\0';
len=strlen(s_new);
for(int i=0;i<len;i++){
if(i<mx)p[i]=min(p[2*id-i],mx-i);
//对称点的半径也就是他的半径;若对称点的半径超出范围;
else p[i]=1;
while(s_new[i+p[i]]==s_new[i-p[i]])p[i]++;
if(mx<i+p[i]){
mx=i+p[i];
id=i;
}
max_len=max(max_len,p[i]-1);
}
return max_len;
}
// #include <iostream>
// #include <cstring>
// #include <algorithm>
// using namespace std;
// char s[1000];
// char s_new[2000];
// int p[2000];
// int Init()
// {
// int len = strlen(s);
// s_new[0] = '$';
// s_new[1] = '#';
// int j = 2;
// for (int i = 0; i < len; i++)
// {
// s_new[j++] = s[i];
// s_new[j++] = '#';
// }
// s_new[j++] = '^'; // 别忘了哦
// s_new[j] = '\0'; // 这是一个好习惯
// return j; // 返回 s_new 的长度
// }
// int Manacher()
// {
// int len = Init(); // 取得新字符串长度并完成向 s_new 的转换
// int max_len = -1; // 最长回文长度
// int id;
// int mx = 0;
// for (int i = 1; i < len; i++)
// {
// if (i < mx)
// p[i] = min(p[2 * id - i], mx - i); // 需搞清楚上面那张图含义,mx 和 2*id-i 的含义
// else
// p[i] = 1;
// while (s_new[i - p[i]] == s_new[i + p[i]]) // 不需边界判断,因为左有 $,右有 ^
// p[i]++;
// // 我们每走一步 i,都要和 mx 比较,我们希望 mx 尽可能的远,
// // 这样才能更有机会执行 if (i < mx)这句代码,从而提高效率
// if (mx < i + p[i])
// {
// id = i;
// mx = i + p[i];
// }
// max_len = max(max_len, p[i] - 1);
// }
// return max_len;
// }
// int main()
// {
// while (printf("请输入字符串:"))
// {
// scanf("%s", s);
// printf("最长回文长度为 %d\n\n", Manacher());
// }
// return 0;
// }