1. violence

Time complexity O(n^3).

2. extension

Centered on a character , Set up left, right Two variables expand out at the same time , Determine if they point to the same character . Pay attention to the discussion of parity . Time complexity O(n^2).

3. Manacher A cart

code annotation ：

``` 1 const int MAXN = 110009;
2 char ma[MAXN * 2];   // Because to add '#', So it's twice the length
3 int mp[MAXN * 2];
4 char s[MAXN];
5
6 void Manacher(char s[], int len) {
7
8     // 1.  Construct string , add to '#', Make the length odd (2 * len - 1)
9     int l = 0;
10     ma[l++] = '\$';   //  Set boundaries
11     ma[l++] = '#';
12     for(int i = 0; i < len; i ++) {
13         ma[l++] = s[i];
14         ma[l++] = '#';
15     }
16     ma[l] = 0;
17
18     //  The core :  Finding palindrome radius ,  The palindrome radius includes the center point
19     int mx = 0; // mx Represents the rightmost value that can be reached
20     int id = 0; // id representative mx Center of
21     for(int i = 0; i < l; i ++) {
22         mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1;
23         while(ma[i + mp[i]] == ma[i - mp[i]]) {
24             mp[i] ++;
25         }
26         if(i + mp[i] > mx) {
27             mx = i + mp[i];
28             id = i;
29         }
30     }
31
32 }
33
34 int main()
35 {
36
37     while(scanf("%s", s) != EOF) {
38         int len = strlen(s);
39         Manacher(s, len);
40         int ans = 0;
41         for(int i = 0; i < 2 * len + 2; i ++) {   //  Find the longest palindrome radius , The length of palindrome string
42             ans = max(ans, mp[i] - 1);  //  Palindrome radius subtraction 1 Is the length of the original palindrome string ( In the palindrome radius, I added #)
43             cout << mp[i] << " ";
44         }
45         printf("%d\n", ans);
46     }
47
48     return 0;
49 }```

Time complexity O(n).

## Judge the longest palindrome string —— violence 、 extension 、Manacher More articles about

1. Manacher Algorithm - Find the longest palindrome string

Find the longest palindrome string - Manacher Algorithm Manacher It is mainly used to find the longest palindrome substring of a string . Don't be manacher The name scares , Actually manacher The algorithm is very simple , And it's easy to understand , The program is short , Time goes back ...

2. Longest Palindrome The longest palindrome string problem

1. subject Given a string s, find the longest palindromic substring in s. You may assume that the maximum ...

3. Algorithm -- The four methods get the longest “ Palindrome string ”, The time complexity is analyzed and compared &amp;PHP

https://blog.csdn.net/hongyuancao/article/details/82962382 “ Palindrome string ” It's a string that is read both forward and backward , such as “level” perhaps “noon” Wait a minute ...

4. MANACHER--- Find the longest palindrome string

Find the longest palindrome string , If it's a violent way , Enumerates each character as the center , Then the longest palindrome string can be detected from both sides , Time complexity in the worst case is 0(n^2), Why is the time complexity so high , Because the detection of each central character is independent ...

5. The longest palindrome string of a string ：Manacher’s Algorithm

Topic link :Longest Palindromic Substring 1. Problem description Given a string S, find the longest palindromic substring ...

6. Leetcode0005--Longest Palindromic Substring Longest palindrome

[ Reprint please indicate ]http://www.cnblogs.com/igoslly/p/8726771.html Take a look at the title : Given a string s, find the longest pali ...

7. Manacher Templates （O（n） Find the length of the longest palindrome string inside ）

from :https://segmentfault.com/a/1190000008484167 /* Because palindromes are divided into even palindromes ( such as bccb) Hoki palindrome ( such as bcacb), And in dealing with parity problems will be more cumbersome , therefore ...

8. ACM subject ———— Longest palindrome

Description Give a small English character a,b,c...y,z Composed string S, seek S The length of the longest palindrome string in . Palindrome is the same string for both positive and negative reading , Such as aba, abba etc.   Input Input has multiple groups cas ...

9. Manacher&#39;s Algorithm Horse drawn car algorithm （ Find the longest palindrome string ）

effect : Find the longest substring in a string , At the same time, we can also find the length of all substrings . Topic link : https://vjudge.net/contest/254692#problem/B The code of the longest palindrome string length : int Man ...

10. （ Longest palindrome Templates ） The longest palindrome -- hdu -- 3068

http://acm.hdu.edu.cn/showproblem.php?pid=3068 The longest palindrome Time Limit: 4000/2000 MS (Java/Others)    Memory ...

## Random recommendation

1. Multithreaded programming - Tools section -BlockingQueue

In the new Concurrent In bag ,BlockingQueue A good solution to multithreading , How to be efficient and safe " transmission " Data problems . Through these efficient and thread safe queue classes , For us to quickly build high-quality multithreaded programs ...

2. JavaWeb Learning notes —— first JSP file

The first sentence must be added to specify the encoding , Otherwise, there will be confusion <%@ page language="java" import="java.util.*" contentT ...

3. Nodejs in cluster Module of the multi process data sharing problem

Nodejs in cluster Module of the multi process data sharing problem Foregoing nodejs stay v0.6.x Then a module was added cluster Used to implement multiple processes , utilize child_process Module to create and manage processes , Add programs in multi-core ...

4. shell The script operates the database regularly

One . Database script (mysql.sh) Linux In the environment , The database A To the database B in #!/bin/bash mysql_host="127.0.0.1" mysql_use ...

5. 【 Reprint 】Mysql binlog relaylog Log migration

background :   By default ,mysql The data of .binlog.relaylog All on the same disk , The path varies according to everyone's settings . When mysql When data or logs in a database grow rapidly , The disk may be out of space or IO Performance follow ...

6. Lottery turntable （jqueryrotate.js）

jqueryrotate.js Lottery turntable , Easy to use , Compatible with all browsers , The effect is as follows <!DOCTYPE> <head> <meta http-equiv="Conten ...

7. postman - Basic operation

Set up the environment collections Import runner Import api To configure api Write tests ( Requests and responses ) Script api Save and export setting file -- setting

8. JS Object oriented and process oriented

Preface object-oriented programming : Is to abstract your requirements into an object , Then analyze the characteristics of the object ( attribute ) With the action ( Method )-- This object is called a class Process oriented programming : characteristic : encapsulation , It is to put the functions you need in an object ------ ...

9. nginx rewrite ( forward )

1.location Regular writing An example : location = / { # Exactly match / , The host name cannot be followed by any string [ configuration A ] } location / { # Because of the ...

10. my C++ The learning

It's the summer vacation of my freshman year to create this blog , This year , I learned my first programming language C++ . C++ Is a programming language that is still active in the forefront of development . Before we start learning it formally , I've heard our seniors complain for a long time C++ It's hard to learn . At first , I ...