Stack and Heap in C and C++

The Stack
It's a special region of your computer's memory that stores temporary variables created by each function (including the main() function). The stack is a "FILO" (first in, last out) data structure, that is managed and optimized by the CPU quite closely. Every time a function declares a new variable, it is "pushed" onto the stack. Then every time a function exits, all of the variables pushed onto the stack by that function, are freed (that is to say, they are deleted). Once a stack variable is freed, that region of memory becomes available for other stack variables.

Variables allocated on the stack, or automatic variables, are stored directly to this memory. Access to this memory is very fast, and it’s allocation is dealt with when the program is compiled.

1. lives in RAM (random-access memory), but has direct support from the processor via its stack pointer.
2. stack pointer is moved down to create new memory and moved up to release that memory.
3. extremely fast and efficient way to allocate storage, second only to registers.
Every thread requires its own stack, they are separated from other stacks, each stack may grow separately.
very fast access
don't have to explicitly de-allocate variables
space is managed efficiently by CPU, memory will not become fragmented
local variables only
limit on stack size (OS-dependent)
variables cannot be resized

The place where arguments of a function call are stored
The place where registers of the calling function are saved
The place where local data of called function is allocated
The place where called function leaves result for calling function
Supports recursive function calls

The Heap
Variables allocated on the heap, or dynamic variables, have their memory allocated at run time (ie: as the program is executing). Accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory. This memory remains allocated until explicitly freed by the program and, as a result, may be accessed outside of the block in which it was allocated.

Heap grows toward stack
All threads share the same heap
Data structures may be passed from one thread to another.
variables can be accessed globally
no limit on memory size
(relatively) slower access
no guaranteed efficient use of space, memory may become fragmented over time as blocks of memory are allocated, then freed
you must manage memory (you're in charge of allocating and freeing variables)
variables can be resized using realloc()

Difference between the stack and the heap
Both Stack and Heap are stored in RAM.
Every thread has its own stack, but all threads in one application shares one heap.
Variable allocation is fast on stack where as on heap its slow.
Variables on stack go out of scope automatically once their need is done. That means de-allocation on stack is automatic. On heap, in regards to C and C++ we have to manually de-allocate where as high-level languages such as Java has garbage collection schemes.
On stack, we can access variables without the need for pointers and hence its fast and that is the reason it is used to store local data, method arguments and the call stack etc all that which needs less amount of memory.
You would use stack only when you know for sure how much memory for your data you would need even before compile time. On the other hand, we can use heap without us having to know for sure the amount of memory we need.
Stack is used for static memory allocation and Heap for dynamic memory allocation.
Stack is thread specific and Heap is application specific.
Memory block in stack will be freed when thread is terminated while heap is freed only after application termination.

Stack Overflow and Heap Overflow(OutOfMemory)

Can an object be stored on the stack instead of the heap?
Yes, an object can be stored on the stack. If you create an object inside a function without using the “new” operator then this will create and store the object on the stack, and not on the heap. Suppose we have a C++ class called Member, for which we want to create an object.

Can the stack grow in size? Can the heap grow in size?
The stack is set to a fixed size, and can not grow past it’s fixed size (although some languages have extensions that do allow this). So, if there is not enough room on the stack to handle the memory being assigned to it, a stack overflow occurs. This often happens when a lot of nested functions are being called, or if there is an infinite recursive call.

If the current size of the heap is too small to accommodate new memory, then more memory can be added to the heap by the operating system.

What can go wrong with the stack and the heap?
If the stack runs out of memory, then this is called a stack overflow – and could cause the program to crash. 
The heap could have the problem of fragmentation, which occurs when the available memory on the heap is being stored as noncontiguous (or disconnected) blocks – because used blocks of memory are in between the unused memory blocks. When excessive fragmentation occurs, allocating new memory may be impossible because of the fact that even though there is enough memory for the desired allocation, there may not be enough memory in one big block for the desired amount of memory.
heap overflow is generally called 'out of memory'.

References
http://www.quora.com/Objective-C-programming-language/What-is-the-difference-between-the-stack-and-the-heap
http://www.programmerinterview.com/index.php/data-structures/difference-between-stack-and-heap/
http://timmurphy.org/2010/08/11/the-difference-between-stack-and-heap-memory-allocation/comment-page-1/

7. Memory : Stack vs Heap

Stack

• very fast access
• don't have to explicitly de-allocate variables
• space is managed efficiently by CPU, memory will not become fragmented
• local variables only
• limit on stack size (OS-dependent)
• variables cannot be resized

Heap

• variables can be accessed globally
• no limit on memory size
• (relatively) slower access
• no guaranteed efficient use of space, memory may become fragmented over time as blocks of memory are allocated, then freed
• you must manage memory (you're in charge of allocating and freeing variables)
• variables can be resized using realloc()

Read full article from 7. Memory : Stack vs Heap

Memory Layout of C Programs | GeeksforGeeks

A typical memory representation of C program consists of following sections.

1. Text Segment:
A text segment , also known as a code segment or simply as text, is one of the sections of a program in an object file or in memory, which contains executable instructions.

As a memory region, a text segment may be placed below the heap or stack in order to prevent heaps and stack overflows from overwriting it.

Usually, the text segment is sharable so that only a single copy needs to be in memory for frequently executed programs.  Also, the text segment is often read-only, to prevent a program from accidentally modifying its instructions.

2. Initialized Data Segment:
Initialized data segment, usually called simply the Data Segment. A data segment is a portion of virtual address space of a program, which contains the global variables and static variables that are initialized by the programmer.

Note that, data segment is not read-only, since the values of the variables can be altered at run time.

This segment can be further classified into initialized read-only area and initialized read-write area.

3. Uninitialized Data Segment:uninitialized data starts at the end of the data segment and contains all global variables and static variables that are initialized to zero or do not have explicit initialization in source code.

4. Stack:
The stack area traditionally adjoined the heap area and grew the opposite direction; when the stack pointer met the heap pointer, free memory was exhausted. 

The stack area contains the program stack, a LIFO structure, typically located in the higher parts of memory. A “stack pointer” register tracks the top of the stack; it is adjusted each time a value is “pushed” onto the stack. The set of values pushed for one function call is termed a “stack frame”; A stack frame consists at minimum of a return address.

Stack, where automatic variables are stored, along with information that is saved each time a function is called. Each time a function is called, the address of where to return to and certain information about the caller’s environment, such as some of the machine registers, are saved on the stack. The newly called function then allocates room on the stack for its automatic and temporary variables. This is how recursive functions in C can work. Each time a recursive function calls itself, a new stack frame is used, so one set of variables doesn’t interfere with the variables from another instance of the function.

5. Heap:
Heap is the segment where dynamic memory allocation usually takes place.

The heap area begins at the end of the BSS segment and grows to larger addresses from there. The Heap area is shared by all shared libraries and dynamically loaded modules in a process.

Read full article from Memory Layout of C Programs | GeeksforGeeks

Unit Testing with JUnit - Tutorial

fail(String) Let the method fail. Might be used to check that a certain part of the code is not reached or to have a failing test before the test code is implemented. The String parameter is optional. assertTrue([message], boolean condition) Checks that the boolean condition is true. assertFalse([message], boolean condition) Checks that the boolean condition is false. assertEquals([String message], expected, actual) Tests that two values are the same. Note: for arrays the reference is checked not the content of the arrays. assertEquals([String message], expected, actual, tolerance) Test that float or double values match. The tolerance is the number of decimals which must be the same. assertNull([message], object) Checks that the object is null. assertNotNull([message], object) Checks that the object is not null. assertSame([String], expected, actual) Checks that both variables refer to the same object. assertNotSame([String], expected, actual)

Read full article from Unit Testing with JUnit - Tutorial

Named Capturing Group in JDK7 RegEx (Xueming Shen's Oracle Blog)

The newly added RegEx constructs to support the named capturing group are:

(1) (?<NAME>X) to define a named group NAME"                     
(2) \\k<Name> to backref a named group "NAME"                  
(3) <$<NAME> to reference to captured group in matcher's replacement str
(4) group(String NAME) to return the captured input subsequence by the given "named group"

With these new constructs, now you can write something like
    String pStr = "0x(?<bytes>\\\\p{XDigit}{1,4})\\\\s++u\\\\+(?<char>\\\\p{XDigit}{4})(?:\\\\s++)?";
    Matcher m = Pattern.compile(pStr).matcher(INPUTTEXT);
    if (m.matches()) {
        int bs = Integer.valueOf(m.group("bytes"), 16);
        int c =  Integer.valueOf(m.group("char"), 16);
        System.out.printf("[%x] -> [%04x]%n", bs, c);
    }

Read full article from Named Capturing Group in JDK7 RegEx (Xueming Shen's Oracle Blog)

Regex Tutorial - Backreferences To Match The Same Text Again

Backreferences match the same text as previously matched by a capturing group. Suppose you want to match a pair of opening and closing HTML tags, and the text in between. By putting the opening tag into a backreference, we can reuse the name of the tag for the closing tag. Here's how: <([A-Z][A-Z0-9]*)\b[^>]*>.*?</\1>.

To figure out the number of a particular backreference, scan the regular expression from left to right. Count the opening parentheses of all the numbered capturing group. The first parenthesis starts backreference number one, the second number two, etc. Skip parentheses that are part of other syntax such as non-capturing groups.

Read full article from Regex Tutorial - Backreferences To Match The Same Text Again

Principles of virtual memory

Basics
1.1. Address translation
1.2. Page table format
2. Replacement algorithms
2.1. FIFO (First in first out)
2.2. LRU (Least recently used)
2.3. Clock
3. Implementation issues
3.1. The translation lookaside buffer
3.2. Table directories
3.3. Inverted page tables
4. Real-world virtual memory
4.1. IA32 page table entries
4.2. Applications of virtual memory

In a very simple operating system, ea

Read full article from Principles of virtual memory

command line - Why hard links are not allowed for directories? - Ask Ubuntu

Symlinks can:

• Point to directories
• Point to non-existent objects
• Point to files and directories outside the same filesystem

Hard links can:

• Keep the file that they reference from being deleted

Hard links are especially useful in performing "copy on write" applications. They allow you to keep a backup copy of a directory structure, while only using space for the files that change between two versions.

The command cp -al is especially useful in this regard. It makes a complete copy of a directory structure, where all the files are represented by hard links to the original files. You can then proceed to update files in the structure, and only the files that you update will take up additional space. This is especially useful when maintaining multigenerational backups.

Read full article from command line - Why hard links are not allowed for directories? - Ask Ubuntu

Difference Between Symbolic Link and Hard Link - Toolbox for IT Groups

* All inodes are created for a filesystem when the filesystem is created.
* Each file, directory, soft link, device, etc. that is tracked by the filesystem is assigned an inode # when it is created. (The filesystem treats all these things as "files.")
* The inode is a data strcuture that keeps track of many pieces of information related to the "file", including user owner and group owner IDs, file type (regular, directory, etc.), size of the file, # of hard links to the file (set to 1 for a regular file with no hard links and incremented for each hard link), disk addresses (where the file is physically located on the disk), etc.

Since each hard link pointing to the same data on the disk uses the same inode # to refer to the data, any change to the data will be seen by ALL users with a hard link to the data (the original file owner and any hard link owners).

What is a hard link? 
A hard link is an additional name for an existing file on Linux or Unix-like OS. Any number of hard links, and thus any number of names, can be created for any file. Hard links can also be created to other hard links. However, they cannot be created for directories, and they cannot cross file system boundaries or span across partitions. 
command: ln file1 hardlink1 

What is a symbolic link? 
Also called soft link, is a special kind of file that points to another file. Unlike a hard link, a symbolic link does not contain the data in the target file. It simply points to another entry somewhere in the file system. 

a.) Soft link files have different inode numbers than source file
b.) The soft link file will be of no use if original file is deleted. 
c.) Soft links are not updated
d.) They can create links between directories
e.) They can cross file system boundaries
Read full article from Difference Between Symbolic Link and Hard Link - Toolbox for IT Groups

In Unix, what is a hard link?

This new link is not a separate copy of the old file, but rather a different name for exactly the same file contents as the old file. Consequently, any changes you make to oldfile will be visible in newlink.

You can use the standard Unix rm command to delete a link. After a link has been removed, the file contents will still exist as long as there is one name referencing the file. Thus, if you use the rm command on a filename, and a separate link exists to the same file contents, you have not really deleted the file; you can still access it through the other link. Consequently, hard links can make it difficult to keep track of files. Furthermore, hard links cannot refer to files located on different computers linked by NFS, nor can they refer to directories. For all of these reasons, you should consider using a symbolic link, also known as a soft link, instead of a hard link.

Read full article from In Unix, what is a hard link?

Why isn't it possible to create hard links across file system boundaries? - nixCraft

A single inode number use to represent file in each file system. All hard links based upon inode number.

So linking across file system will lead into confusing references for UNIX or Linux.

Read full article from Why isn’t it possible to create hard links across file system boundaries? - nixCraft

Why is it possible to create symbolic links across file system boundaries?

Symbolic links link by pathname rather than inode number. As you know, each pathname is a unique file on a system. Because of this, it is possible to create symbolic links across file system boundaries.

Read full article from Why is it possible to create symbolic links across file system boundaries?

Understanding UNIX / Linux symbolic (soft) and hard links - nixCraft

• Hard links cannot link directories.
• Cannot cross file system boundaries.

Soft or symbolic links are just like hard links. It allows to associate multiple filenames with a single file. However, symbolic links allows:

• To create links between directories.
• Can cross file system boundaries.

These links behave differently when the source of the link is moved or removed.

• Symbolic links are not updated.
• Hard links always refer to the source, even if moved or removed.

Read full article from Understanding UNIX / Linux symbolic (soft) and hard links - nixCraft

Understanding UNIX / Linux filesystem Inodes - nixCraft

The inode identifies the file and its attributes (as above) . Each inode is identified by a unique inode number within the file system. Inode is also know as index number.
An inode is a data structure on a traditional Unix-style file system such as UFS or ext3. An inode stores basic information about a regular file, directory, or other file system object.
You can use ls -i command to see inode number of file
ls -i /etc/passwd
You can also use stat command to find out inode number and its attribute:
stat /etc/passwd

Inode application
Many commands used by system administrators in UNIX / Linux operating systems often give inode numbers to designate a file.
cd /tmp
touch \"la*
ls -l
Now try to remove file "la*
You can't, to remove files having created with control characters or characters which are unable to be input on a keyboard or special character such as ?, * ^ etc. You have to use inode number to remove file.
Read full article from Understanding UNIX / Linux filesystem Inodes - nixCraft

Javarevisited: 5 example of sort command in UNIX or Linux >>>> Unix Tutorial

▼ Friday, August 26, 2011 5 example of sort command in UNIX or Linux >>>> Unix Tutorial Sorting is one of essential task we always need to perform and UNIX or Linux has great support for sorting by using sort command. No matter what kind of shell script you are writing or you are looking for some information or reports many times you need to sort the output from one command or a set of line, with combination of sort with find command and grep in unix you can handle support request and reporting quite easily.

Read full article from Javarevisited: 5 example of sort command in UNIX or Linux >>>> Unix Tutorial

Javarevisited: How to find file and directory size in Unix with Example - Linux tutorial

▼ Friday, March 23, 2012 How to find file and directory size in Unix with Example - Linux tutorial How to find size of directory in unix Finding file size or directory size in Unix and Linux is not very difficult but if you came from windows background than it may sounds difficult to you because you need to remember unix commands for file and directory size. This is a common complain from windows user when they exposed to Unix operating system be it Linux or Solaris.

Read full article from Javarevisited: How to find file and directory size in Unix with Example - Linux tutorial

10 xargs command example in Linux - Unix tutorial

with and without xargs
you can clearly see that multiline output is converted into single line:
find . -name "*bash*" | xargs
xargs and grep
find . -name "*.java" | xargs grep "Stock"
delete temporary file using find and xargs
find /tmp -name "*.tmp" | xargs rm
xargs -0 to handle space in file name
find /tmp -name "*.tmp" -print0 | xargs -0 rm
xargs and cut command in Unix
cut -d, -f1 smartphones.csv | sort | xargs
Counting number of lines in each file using xargs and find
ls -1 *.txt | xargs wc -l
Passing subset of arguments to xargs in Linux.
when used with xargs you can use flag "-n" to instruct xargs on how many argument it should pass to given command. this xargs command line option is extremely useful on certain situation like repeatedly doing diff etc
ls -1 *.txt | xargs -n 2 echo
avoid "Argument list too long"
xargs in unix or Linux was initially use to avoid "Argument list too long" errors and by using xargs you send sub-list to any command which is shorter than "ARG_MAX" and that's how xargs avoid "Argument list too long" error. You can see current value of "ARG_MAX" by using getconf ARG_MAX.

find –exec vs find + xargs

xargs with find command is much faster than using -exec on find. since -exec runs for each file while xargs operates on sub-list level. to give an example if you need to change permission of 10000 files xargs with find will be almost 10K time faster than find with -exec because xargs change permission of all file at once

Read full article from 10 xargs command example in Linux - Unix tutorial

xargs: How To Control and Use Command Line Arguments

utility. xargs reads items from the standard input or pipes, delimited by blanks or newlines, and executes the command one or more times with any initial-arguments followed by items read from standard input. Blank lines on the standard input are ignored.
echo 1 2 3 4 | xargs echo
Find all .bak files in or below the current directory and delete them.
find . -name "*.bak" -type f -print | xargs /bin/rm -f
{} as the argument list marker
{} is the default argument list marker. You need to use {} this with various command which take more than two arguments at a time. For example mv command need to know the file name. The following will find all .bak files in or below the current directory and move them to ~/.old.files directory:
find . -name "*.bak" -print0 | xargs -0 -I {} mv {} ~/old.files
You can rename {} to something else. In the following example {} is renamed as file. This is more readable as compare to previous example:
find . -name "*.bak" -print0 | xargs -0 -I file mv file ~/old.files
Avoiding errors and resource hungry problems with xargs and find combo
find /share/media/mp3/ -type f -name "*.mp3" -print0 | xargs -0 -r -I file cp -v -p file --target-directory=/bakup/iscsi/mp3

Reference: http://www.computerhope.com/unix/xargs.htm
--null, -0 Input items are terminated by a null character instead of by whitespace, and the quotes and backslash are not special (every character is taken literally). Disables the end-of-file string, which is treated like any other argument. Useful when input items might contain white space, quote marks, or backslashes. The find -print0 option produces input suitable for this mode.

find /tmp -name core -type f -print | xargs /bin/rm -f
Find files named core in or below the directory /tmp and delete them. (Note that this will work incorrectly if there are any filenames containing newlines or spaces.)
find /tmp -name core -type f -print0 | xargs -0 /bin/rm -f
find /tmp -depth -name core -type f -delete
Find files named core in or below the directory /tmp and delete them, but more efficiently than in the previous example (because we avoid the need to use fork and exec rm, and we don't need the extra xargs process).
cut -d: -f1 < /etc/passwd | sort | xargs echo
Uses cut to generate a compact listing of all the users on the system.

Read full article from xargs: How To Control and Use Command Line Arguments

10 Example of find command in Unix and Linux

How to find files which has been modified less than one day, minute or hour  in Unix:
find . -mtime 1  (find all the files modified exact 1 day)
find . -mtime -1 (find all the files modified less than 1 day)
find . -mtime +1 (find all the files modified more than 1 day)

How to find all the files and directories which holds the 777 permission
find . -perm 644

Case insensitive search using find
How to do case insensitive search using find command in Unix? Use option “-i" with name, by default find searches are case sensitive. This option of find is extremely helpful while looking for errors and exceptions in log file.
find . –iname "error" –print ( -i is for ignore )

How to find files based on size in Unix and Linux
find . -size +1000c -exec ls -l {} \;
find . -size +10000c -size -50000c -print
The minus sign means "less than," and the plus sign means "greater than."
This find example lists all files that are greater than 10,000 bytes, but less than 50,000 bytes.

How to find files some days older and above certain size
find . -mtime +10 -size +50000c -exec ls -l {} \;

How to use find command on file names with space
find . -name "*equity*" -print
find . -name "*equity*" -print | xargs ls -l
find . -name "*equity*" -print0 | xargs ls
Read full article from 10 Example of find command in Unix and Linux

LeetCode - Longest Palindromic Substring | Darren's Blog

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Brute Force: Enumerate every possible substring, and verify whether it is palindromic. The number of possible subtrings is C(n,2)=O(n2) , and verifying each substring takes O(n) time. As a result, its time complexity isO(n3)

public String longestPalindrome(String s) {

    int length = s.length();

    int longestStart = 0, longestEnd = 0;

    // Enumerate every possible substring with start index i and end index j

    for (int i = 0; i < length; i++) {

        for (int j = i; j < length; j++) {

            // s_i...s_j is a palindrome of longer length

            if (isPalindromic(s, i, j) && j-i > longestEnd-longestStart) {

                longestStart = i;

                longestEnd = j;

            }

        }

    }

    return s.substring(longestStart, longestEnd+1);

}

Dynamic Programming: Let p[i,j] denote whether the substring Si…Sj is palindromic. It can be observed that p[i,j] is true if and only if p[i+1,j−1] is true and Si=Sj . The base cases for this recursion are that p[i,i] is true and that p[i,i+1] is true if and only if Si=Si+1

public String longestPalindrome(String s) {

    int n = s.length();

    int longestLength = 1, longestStart = 0;

    // Create and initialize the table

    boolean[][] p = new boolean[n][n];

    for (int i = 0; i < n; i++)

        p[i][i] = true;         // s_i is a palindrome

    for (int i = 0; i < n-1; i++) {

        // s_i,s_{i+1} is a palindrome iff s_i == s_{i+1}

        if (s.charAt(i) == s.charAt(i+1)) {

            p[i][i+1] = true;

            longestLength = 2;

            longestStart = i;

        }

    }

    // Fill the table by ascending order of substring length

    for (int len = 3; len <= n; len++) {

        for (int i = 0; i < n-len+1; i++) {

            int j = i + len - 1;

            // s_i...s_j is a palindrome iff s_{i+1}...s_{j-1} is palindrome and s_i == s_j

            if (p[i+1][j-1] && s.charAt(i) == s.charAt(j)) {

                p[i][j] = true;

                longestLength = len;

                longestStart = i;

            }

        }

    }

 

    return s.substring(longestStart, longestStart+longestLength);

}

• Center Expansion: We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center. Note that 2n−1centers is available, considering the ones between two adjacent characters. As such, O(n2) time and O(1) space is achieved.

Code from http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html

string expandAroundCenter(string s, int c1, int c2) {

  int l = c1, r = c2;

  int n = s.length();

  while (l >= 0 && r <= n-1 && s[l] == s[r]) {

    l--;

    r++;

  }

  return s.substr(l+1, r-l-1);

}

 

string longestPalindromeSimple(string s) {

  int n = s.length();

  if (n == 0) return "";

  string longest = s.substr(0, 1);  // a single char itself is a palindrome

  for (int i = 0; i < n-1; i++) {

    string p1 = expandAroundCenter(s, i, i);

    if (p1.length() > longest.length())

      longest = p1;

 

    string p2 = expandAroundCenter(s, i, i+1);

    if (p2.length() > longest.length())

      longest = p2;

  }

  return longest;

}

Manacher’s Algorithm: It takes advantages of palindrome's symmetric property and avoids some unnecessary computations.

public String longestPalindrome(String s) {

    String t = preProcess(s);

    int n = t.length();

    int[] p = new int[n];

    int center = 0, right = 0;

    for (int i = 1; i < n-1; i++) {

        int mirror = 2 * center - i;

        p[i] = (right > i) ? Math.min(right-i, p[mirror]) : 0;

        // Attempt to expand the palindrome centered at index i

        while (t.charAt(i+p[i]+1) == t.charAt(i-p[i]-1))

            p[i]++;

 

        // Adjust center and right edge if necessary

        if (i + p[i] > right) {

            center = i;

            right = i + p[i];

        }

    }

    // Find the length of the longest palindrome, and the start index of it

    int longestLength = 0, longestStart = 0;

    for (int i = 1; i< n-1; i++) {

        if (p[i] > longestLength) {

            longestLength = p[i];

            longestStart = (i-1-longestLength) / 2;

        }

    }

 

    return s.substring(longestStart, longestStart+longestLength);

}

 

// Add "#" betweeen characters,

// and "^" and "$" as the start and end sntinels, respectively

private String preProcess(String s) {

    int n = s.length();

    if (n == 0)

        return "^$";

    String result = "^";

    for (int i = 0; i < n; i++)

        result += "#" + s.charAt(i);

    result += "#$";

    return result;

}

Suffix Trees: As said in the Wikipedia page, there exists a linear solution base on suffix trees, which I have not investigated yet.
Read full article from LeetCode - Longest Palindromic Substring | Darren's Blog