商业网站运营成本,凡科网之前做的网站在哪看,利用网站宣传 两学一做,腾讯企点是干嘛的题面#xff1a; 洛谷#xff1a;[SHOI2011]双倍回文‘ 题解#xff1a; 首先有一个性质#xff0c;本质不同的回文串最多O(n)个。 所以我们可以对于每个i#xff0c;求出以这个i为结尾的最长回文串#xff0c;然后以此作为长串#xff0c;并判断把这个长串从中间劈开后…题面 洛谷[SHOI2011]双倍回文‘ 题解 首先有一个性质本质不同的回文串最多O(n)个。 所以我们可以对于每个i求出以这个i为结尾的最长回文串然后以此作为长串并判断把这个长串从中间劈开后左边的一半是否也是一个回文串判断左边那半的中点的回文半径是否可以跨过当前长串的中点。 复杂度O(n) 1 // luogu-judger-enable-o22 #includebits/stdc.h3 using namespace std;4 #define R register int5 #define AC 10010006 7 int n, pos, maxn, ans;8 int r[AC];9 char a[AC], s[AC];
10
11 void pre(){
12 scanf(%d%s, n, a 1);
13 s[0] $, s[1] #;
14 for(R i 1; i n; i ) s[2 * i] a[i], s[2 * i 1] #;
15 }
16
17 inline void upmax(int a, int b){
18 if(b a) a b;
19 }
20
21 void manacher()
22 {
23 int b 2 * n;
24 for(R i 1; i b; i )
25 {
26 r[i] (maxn i) ? min(r[2 * pos - i], maxn - i 1) : 1;//这里要取min
27 while(s[i - r[i]] s[i r[i]]) r[i];
28
29 int last i - r[i] 1, Next i r[i] - 1;
30 if(s[last] #) last, -- Next;
31 if(i r[i] - 1 maxn last i)//last才是整个串的开头
32 {
33 for(R j maxn 1; j Next; j )
34 {
35 int l 2 * i - j;//获取串头
36 int sum (j - l 1 1) 1;
37 if(s[j] # || sum % 4) continue;//中间是获取实际字符数
38 int tmp (l j) 1, k (tmp l) 1;
39 if(k r[k] - 1 tmp) upmax(ans, sum);
40 }
41 }
42
43 if(i r[i] - 1 maxn) pos i, maxn i r[i] - 1;
44 }
45 printf(%d\n, ans);
46 }
47
48 int main()
49 {
50 //freopen(in.in, r, stdin);
51 pre();
52 manacher();
53 //fclose(stdin);
54 return 0;
55 } View Code 转载于:https://www.cnblogs.com/ww3113306/p/10066792.html
