Coders Packet

Smallest KMP in C++

By Ayush Agrawal

This project is an improvised version of the renowned KMP (Knuth-Morris-Pratt) algorithm.

As we know, the KMP algorithm searches for the occurrences of a "word" W within a main "text string" S with having a worst-case time complexity of O(n).

The basic idea behind this project is to find the lexicographically smallest anagram of "text string" S that contains "word" W as a substring.

The program takes S and W as input strings respectively and prints the lexicographically smallest anagram of S containing W as its substring.


> 1<=|P|<=|S|<=100000

> S and P can possess only lowercase English letters

> there is at least one anagram of S that contains P

The time complexity of the program is O(n).

Download Complete Code


No comments yet