1. 引言     本KMP原文最初写于2年多前的2011年12月,因当时初次接触KMP,思路混乱导致写也写得混乱。所以一直想找机会重新写下KMP,但苦于一直以来对KMP的理解始终不够,故才迟迟没有修改本文。     然近期因开了个算法班,班上专门讲解数据结构、面试、算法,才再次仔细回顾了这个KMP,在综合了一些网友的理解、以及算法班的两位讲师朋友曹博、邹博的理解之后,写了9张PPT,发在微博上。随后,一不做二不休,索性将PPT上的内容整理到了本文之中(后来文章越写越完整,所…

2016年11月6日 0条评论 3点热度 阅读全文

1 分治算法 一、基本概念    在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……     任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解…

2016年9月7日 0条评论 8点热度 阅读全文