# Introduction

Given two strings s1 and s2, find if s1 is a substring of s2.

# Approach

We can use the KMP Algorithm. The idea behind KMP is “recovering” from mismatches by using partial match information to skip over positions where the pattern can’t possibly be found and avoid redoing comparisons where we already know that a prefix of the pattern matches the main string.

In computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
The algorithm was conceived by James H. Morris and independently discovered by Donald Knuth "a few weeks later" from automata theory. Morris and Vaughan Pratt published a technical report in 1970. The three also published the algorithm jointly in 1977.

KMP is done using the LPS (longest possible suffix which is also a prefix), also thought as a Partial Match Table.

Refer to the the previous article for Find the continuous pattern in a given string.

Proper prefix: All the characters in a string, with one or more cut off the end. “S”, “Sn”, “Sna”, and “Snap” are all the proper prefixes of “Snape”.

Proper prefix: All the characters in a string, with one or more cut off the end. “S”, “Sn”, “Sna”, and “Snap” are all the proper prefixes of “Snape”.

Proper suffix: All the characters in a string, with one or more cut off the beginning. “agrid”, “grid”, “rid”, “id”, and “d” are all proper suffixes of “Hagrid”.

The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern.

1. aba - longest prefix and longest suffix that are equal `a` length is 1
2. abba - longest prefix and longest suffix that are equal `ab` length is 2
3. ababa -  longest prefix and longest suffix that are equal `aba` length is 3

## Example

`W` = "ABCDABD" and `S` = "ABC ABCDAB ABCDABCDABDE"

# Code

We compute the Partial Match Table (LPS) and we sue it to perform the substring search. For any mismatch, we try to move the pattern based on the LPS, or increment the main string index otherwise.