KMP

Knuth–Morris–Pratt algorithm

Text of length T, pattern of length P.

Brute force: O(|T|.|P|)

KMP: O(|T|+|P|)

Tries: O(|P|)

References:

1. http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm