字符串匹配广泛用于各类工程、研究。朴素的字符串匹配像极了两条履带，小的履带先和大的履带对齐，逐个验证上下是否一致。如果不一致，小的履带右移一格，继续上下比对。最坏复杂度是O（nm），实在难以让人满意。
实际上，小履带没必要每次都从头开始和大履带匹配，假设小履带已经匹配了好多，失配后右移一位从头开始走，有一大半点都是和小履带自己在匹配。 这不坑爹么，根本没有用到大履带，为何要放到大履带的循环里呢？这部分完全可以做个预处理，下次直接跳到和大履带比对的点就行了。这就是KMP的getfail函数。
void getFail(string str){ f[0]=0;f[1]=0; for(int i=1;i getfail函数采用类似动态规划的思想，记录每次应该跳跃到的点。
int KMP(string obj,string ask,int pos){ getFail(ask); int j=0; int n=obj.size(); for(int i=pos;i 匹配的时候直接从f记录的点开始，省去不少麻烦。
@练习题
HDU 3336
POJ 1961