Through the storm, we will find a way.

一寸先が闇なら、二寸先は明るい未来

始まりと終わりのプロローグ

-Turning Point-

いつの日かdistanceも

抱きしめられるようになれるよ

介绍

利用哈希的思想，实现快速判断两个字符串是否相同。

介绍

trie，又称前缀树或字典树，是一种有序树，用来保存关联数组，其中的键通常是字符串。是一种高效的存储和查找字符串的数据结构。

Introduction

Presume we have a string S (length is m) and a pattern P (length is n) given as follow:

1
2
3

index: 1  2  3  4  5  6  7  8  9  10 11 12
S:     a  b  a  b  a  a  b  a  a  b  a  c
P:     a  b  a  a  b  a  c

Now we want to find out is there a sub-string in S that matchs P exactly, which in this case is S[6:12].

That is what KMP algorithm does.