string algorithm - OpenGenus IQ: Learn Computer Science

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.

algorithm

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

algorithm

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

algorithm

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.

algorithm

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

algorithm

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

algorithm

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.

algorithm

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

algorithm

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.

algorithm

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.

string algorithm

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

string algorithm

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.

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