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 ...