Palindromes | Problems on strings

Longest palindromic substring

In computer science, the longest palindromic substring or longest symmetric factor problem is the problem of finding a maximum-length contiguous substring of a given string that is also a palindrome. For example, the longest palindromic substring of "bananas" is "anana". The longest palindromic substring is not guaranteed to be unique; for example, in the string "abracadabra", there is no palindromic substring with length greater than three, but there are two palindromic substrings with length three, namely, "aca" and "ada". In some applications it may be necessary to return all maximal palindromic substrings (that is, all substrings that are themselves palindromes and cannot be extended to larger palindromic substrings) rather than returning only one substring or returning the maximum length of a palindromic substring. invented an -time algorithm for listing all the palindromes that appear at the start of a given string of length . However, as observed e.g., by , the same algorithm can also be used to find all maximal palindromic substrings anywhere within the input string, again in time. Therefore, it provides an -time solution to the longest palindromic substring problem. Alternative -time solutions were provided by , and by , who described a solution based on suffix trees. A faster algorithm can be achieved in the word RAM model of computation if the size of the input alphabet is in . In particular, this algorithm runs in time using space. Efficient parallel algorithms are also known for the problem. The longest palindromic substring problem should not be confused with the different problem of finding the longest palindromic subsequence. (Wikipedia).

Video thumbnail

Python Programming Practice: LeetCode #5 -- Longest Palindromic Substring

This episode of Python Programming Practice shows two approaches to LeetCode #5 -- Longest Palindromic Substring https://leetcode.com/problems/longest-palindromic-substring/ This is a medium difficulty problem. Note that the intent of this series to help viewers think through approaches

From playlist Python Programming Practice

Video thumbnail

Longest common substring problem suffix array

Related Videos: Suffix array intro: https://www.youtube.com/watch?v=zqKlL3ZpTqs Longest common prefix (LCP) array: https://www.youtube.com/watch?v=53VIWj8ksyI Counting unique substrings: https://www.youtube.com/watch?v=m2lZRmMjebw Longest common substring 1/2: https://www.youtube.com/watch

From playlist Data structures playlist

Video thumbnail

Longest common substring problem suffix array part 2

Related Videos: Suffix array intro: https://www.youtube.com/watch?v=zqKlL3ZpTqs Longest common prefix (LCP) array: https://www.youtube.com/watch?v=53VIWj8ksyI Counting unique substrings: https://www.youtube.com/watch?v=m2lZRmMjebw Longest common substring 1/2: https://www.youtube.com/watch

From playlist Data structures playlist

Video thumbnail

Suffix array introduction

Related Videos: Suffix array intro: https://www.youtube.com/watch?v=zqKlL3ZpTqs Longest common prefix (LCP) array: https://www.youtube.com/watch?v=53VIWj8ksyI Counting unique substrings: https://www.youtube.com/watch?v=m2lZRmMjebw Longest common substring 1/2: https://www.youtube.com/watch

From playlist Data structures playlist

Video thumbnail

Longest Repeated Substring suffix array

Related Videos: Suffix array intro: https://www.youtube.com/watch?v=zqKlL3ZpTqs Longest common prefix (LCP) array: https://www.youtube.com/watch?v=53VIWj8ksyI Counting unique substrings: https://www.youtube.com/watch?v=m2lZRmMjebw Longest common substring 1/2: https://www.youtube.com/watch

From playlist Data structures playlist

Video thumbnail

Lecture 7 - Suffix Arrays and Assembly

This is Lecture 7 of the CSE549 (Computational Biology) course taught by Professor Steven Skiena [http://www.cs.sunysb.edu/~skiena/] at Stony Brook University in 2010. The lecture slides are available at: http://www.algorithm.cs.sunysb.edu/computationalbiology/pdf/lecture7.pdf More infor

From playlist CSE549 - Computational Biology - 2010 SBU

Video thumbnail

Data Science with Mathematica -- Dynamic Programming

In this session of my Data Science with Mathematica track I provide an introduction to Dynamic Programming for the Data Scientist. DP is a very important, practical, flexible, and code-efficient way to solve problems in combinatorial optimization. Its applicability covers many fields: oper

From playlist Data Science with Mathematica

Video thumbnail

Longest Common Prefix (LCP) array

Related Videos: Suffix array intro: https://www.youtube.com/watch?v=zqKlL3ZpTqs Longest common prefix (LCP) array: https://www.youtube.com/watch?v=53VIWj8ksyI Counting unique substrings: https://www.youtube.com/watch?v=m2lZRmMjebw Longest common substring 1/2: https://www.youtube.com/watch

From playlist Data structures playlist

Video thumbnail

Lecture 6 - Suffix Trees in Action

This is Lecture 6 of the CSE549 (Computational Biology) course taught by Professor Steven Skiena [http://www.cs.sunysb.edu/~skiena/] at Stony Brook University in 2010. The lecture slides are available at: http://www.algorithm.cs.sunysb.edu/computationalbiology/pdf/lecture6.pdf More infor

From playlist CSE549 - Computational Biology - 2010 SBU

Video thumbnail

Suffix array finding unique substrings

Related Videos: Suffix array intro: https://www.youtube.com/watch?v=zqKlL3ZpTqs Longest common prefix (LCP) array: https://www.youtube.com/watch?v=53VIWj8ksyI Counting unique substrings: https://www.youtube.com/watch?v=m2lZRmMjebw Longest common substring 1/2: https://www.youtube.com/watch

From playlist Data structures playlist

Video thumbnail

Lecture 12 | Programming Methodology (Stanford)

Lecture by Professor Mehran Sahami for the Stanford Computer Science Department (CS106A). Professor Sahami lectures on Enumeration. CS106A is an Introduction to the engineering of computer applications emphasizing modern software engineering principles: object-oriented design, decomposi

From playlist Course | Programming Methodology

Video thumbnail

Longest Common Substring | Dynamic Programming | Data Structures And Algorithms | Simplilearn

This video on longest common substring will acquaint you with a clear understanding of the longest common substring and solution implementation. In this Data Structure and Algorithm Tutorial, you will understand a different aspect to dynamic programming and how to utilize it to find longes

From playlist 🔥Python | Python Tutorial For Beginners | Python Projects | Python Interview Questions And Answers | Updated Python Playlist 2023 | Simplilearn

Video thumbnail

Java String Programs | String Examples in Java | Java Certification Training | Edureka

🔥 Java Certification Training: https://www.edureka.co/java-j2ee-training-course This Edureka video on Java String Programs will talk about top 10 important programs in java strings with examples. Below programs are covered in this video: Reverse words in a String String Concatenation Frequ

From playlist Java Tutorial For Beginners | Edureka

Video thumbnail

Java String Programs For Beginners | Java String Examples | Java Training | Edureka | Java Rewind -1

🔥Java Certification Training: https://www.edureka.co/java-j2ee-training-course This Edureka video on Java String Programs will talk about top 10 important programs in java strings with examples. 🔴Subscribe to our channel to get video updates. Hit the subscribe button above: https://goo.g

From playlist Edureka Live Classes 2020

Video thumbnail

STRINGS and LANGUAGES - Formal Languages and Automata

We talk all about strings, alphabets, and languages. We cover length, concatenation, substrings, and reversals. We also talk about palindromes! 0:00 - [Intro] 2:54 - [Length of a String] 4:40 - [Reverse of a String] 7:48 - [Substrings] 10:06 - [Concatenation] 13:04 - [Summative Exercise]

From playlist Formal Languages and Automata

Video thumbnail

Using a set of points determine if the figure is a parallelogram using the midpoint formula

👉 Learn how to determine the figure given four points. A quadrilateral is a polygon with four sides. Some of the types of quadrilaterals are: parallelogram, square, rectangle, rhombus, kite, trapezoid, etc. Each of the types of quadrilateral has its properties. Given four points that repr

From playlist Quadrilaterals on a Coordinate Plane

Video thumbnail

Srecko Brlek: Palindromes patterns

Abstract: The study of palindromes and their generalizations in a word has gained a lot of interest in the last 20 years, motivated by applications in physics, biology, discrete geometry, to name only a few. Using Sebastien Ferenczi as an example, we illustrate the computation of its palin

From playlist Dynamical Systems and Ordinary Differential Equations

Video thumbnail

The World's Longest Bridges

We look at the longest bridges in the world by construction type. For more by The B1M subscribe now - http://ow.ly/GxW7y Read the full story on this video, including images and useful links, here: http://www.theb1m.com/video/the-worlds-longest-bridges The Golden Gate - Building an Impos

From playlist The World's...

Video thumbnail

MegaFavNumbers - 1030301

This video is part of the MegaFavNumbers project. Maths YouTubers have come together to make videos about their favourite numbers bigger than one million, which we are calling #MegaFavNumbers. This is my contribution to the project. It is about the number 1030301, which has some amazing

From playlist MegaFavNumbers

Related pages

Palindrome | Suffix tree | Substring | Parallel algorithm | Subsequence | Word RAM