×
Home Discussions Write at Opengenus IQ
×
  • #7daysOfCode
  • C Interview questions
  • Linux 💽
  • 🔊 Data Structures
  • Graph Algorithms
  • Dynamic Programming 💑
  • Greedy Algo 📔
  • Algo Book 🧠
  • String Algo 🧬
  • Join our Internship 🎓
  • Home

String Algorithms

String Algorithms are algorithms to perform specify tasks on strings such as string pattern matching, searching string data and much more.

Algorithms

Longest common substring using rolling hash approach

We can solve the longest common substring problem using the rolling hash technique in O(N * log(N)^2) time and O(N) space which is significantly better than other approaches.

Ashutosh Singh Ashutosh Singh
Algorithms

Find number of substrings with same first and last characters

You are given a string lets say "S" , you need to find the number of all contiguous substrings (part of "S") starting and ending with the same character.

Shubham Kumar
Algorithms

Word Break Problem

In this article we are going to talk about a very interesting problem: Word Break Problem. This can be solved using Dynamic Programming [O(N^2) time, O(N^2) space].

Ayush Mehar
Software Engineering

Reverse a String (word by word) in C

In this problem, we have reversed a string or text word by word in C. The strategy to do this is important and tests C implementation skill.

Abhiram Reddy Duggempudi Abhiram Reddy Duggempudi
Algorithms

Number of times characters of a string is present in another string

In this article, we have explored the algorithm to find the Number of times characters of a string is present in another string. This can be solved in O(N^2) time.

Abhiram Reddy Duggempudi Abhiram Reddy Duggempudi
Algorithms

First Unique Character in a String

In this article, we need to find first unique i.e non-repeating character in a given string and return the index or else if no such character exists we return -1.

Abhiram Reddy Duggempudi Abhiram Reddy Duggempudi
Algorithms

String Matching using Bitset

In this article, we have explored how to solve string matching problem (find all occurences of string S1 in another string S2) using Bitset. It is a modification of the naive approach which takes O(L x P x logL) time complexity which improves to O(L x P / K) using bitset.

Anand Saminathan
Algorithms

Knuth-Morris-Pratt (KMP) vs Boyer Moore Pattern Searching algorithm

In this article, we have explored the difference between two popular string pattern searching algorithms: Knuth-Morris-Pratt (KMP) vs Boyer Moore Pattern Searching algorithm.

Sweta Behera
Algorithms

Minimum characters added to the front of string to make it palindrome

In this problem, we have to formulate an algorithm to find the minimum number of characters to be added to the front of a string to make it a palindrome. To solve this efficiently in linear time O(N), we have to use longest prefix suffix of Knuth Morris Pratt pattern matching algorithm.

Shujaa Ahmad Shujaa Ahmad
Algorithms

Minimum insertions to make the frequency of each character unique

We developed a string algorithm to find out the minimum number of insertions to be made in a string so that the frequency of each character is unique

Shubham Kumar Shubham Kumar
Algorithms

Minimum deletions to make frequency of each character unique

The problem we will solve is that given a string s, we need to find the minimum number of characters to be deleted from s so that the frequency of each character in the string is unique.

Shubham Kumar Shubham Kumar
Algorithms

Find if a string is a sub-string of another string

We have presented two approaches to check whether a string is a substring of another string namely naive method which takes O(N^2) time and efficient method using the concept of Rolling Hash which takes linear time O(N).

Ashutosh Singh Ashutosh Singh
Algorithms

Rolling Hash

Rolling hash is an algorithmic technique which is used to prevent rehashing the whole string while calculating hash values of the substrings of a given string

Ashutosh Singh Ashutosh Singh
Algorithms

Longest repeating and non overlapping substring in a string

We have to find the longest repeating and non-overlapping substring in a given string. Brute force approach takes O(N^3) time while Dynamic Programming takes O(N^2) time.

Ashutosh Singh Ashutosh Singh
Algorithms

String hashing

Hashing is an important technique which converts any object into an integer of a given range. Hashing is the key idea behind Hash Maps which provides searching in any dataset in O(1) time complexity. An efficient algorithm to hash a string is used to compare strings in O(1) time complexity

OpenGenus Foundation OpenGenus Foundation
Algorithms

Aho Corasick Algorithm

Aho Corasick algorithm is a string algorithm to find or search occurrences of k number of Patterns: P1 ,P2 .... Pk in a string text T. It is a modification over the KMP algorithm

Aman Agarwal Aman Agarwal
Algorithms

Manacher's Algorithm

Manacher's Algorithm is an efficient algorithm to find the longest palindromic substring in a given string in linear time and linear space complexity. It uses key ideas from dynamic programming to solve the problem efficiently.

Piyush Mittal Piyush Mittal
Algorithms

Boyer Moore String Search Algorithm

Boyer Moore string search algorithm is an efficient string searching algorithm which was developed by Robert S. Boyer and J Strother Moore in 1977. The time complexity is linear in terms of length of data to be searched and preprocessing complexity is linear as well

Piyush Mittal Piyush Mittal
Algorithms

KMP (Knuth-Morris-Pratt) Algorithm

Given a string S of length n and a pattern P of length m , you have to find all occurences of pattern P in string S provided n > m. Knuth Morris Pratt algorithm is an efficient pattern searching algorithm. Time and space complexity of KMP algorithm is O(m + n) linear.

Piyush Mittal Piyush Mittal
Algorithms

Rabin-Karp Pattern Searching Algorithm

Rabin-Karp Algorithm is an efficient string pattern searching algorithm that utilizes the technique of hashing to search for patterns in a string in linear time by using a clever way of calculating hashes. This algorithm has been developed by Richard M. Karp and Michael O. Rabin in 1987.

Aman Agarwal Aman Agarwal
String Algorithms

Algorithm to find the maximum occurring character in a string

Algorithm Pseudocode Complexity Implementation Applications Reading time: 15 minutes | Coding time: 5 minutes One approach to solve this problem would be to sort the input string and then traverse through the sorted string

Akash A. Gajjar Akash A. Gajjar
String Algorithms

Z Algorithm function

The Z-function for a string S of length N is an array of length N where the i th element is equal to the greatest number of characters starting from the position i that coincide with the first characters of S.

OpenGenus Foundation OpenGenus Foundation
suffix array

Suffix Array

A Suffix Array contains integers that represent the starting indices of all the suffixes of a given string, after the aforementioned suffixes have been sorted. There are two approaches to compute: O(N^2 * log N) and O(N * log N * log N) approach. Locate every occurrence of a pattern within a string

OpenGenus Foundation OpenGenus Foundation
×

Visit our discussion forum to ask any question and join our community

View Forum
OpenGenus IQ © 2021 All rights reserved â„¢ [email: team@opengenus.org]
Top Posts LinkedIn Twitter