Knuth–Morris–Pratt (KMP) algorithm

Learnt from LeetCode question Linked List in Binary Tree. A faster way to check string patten against a given text.

First round, iterate through pattern to generate a new array for later use. Intuition behind this is to find same suffix and prefix so at the second round we don’t go back in given text for duplicate substring.

Second round, we compare given text against pattern with the help of the generated array.

The total time complexity will be O(m+n), m being the length of given text and n being the length of pattern, which is a large improvement compared with the brute force way (O(m*n)).