<commit_before>﻿---
layout: post
title: LaTeX beamer制作幻灯片
category: 技术
tags: LaTeX
keywords: 
description: 
---


###说明
关于KMP算法，网上资料很多，但讲明白的似乎并不是很多([Matrix67](http://www.matrix67.com/blog/archives/115)大牛那篇关于KMP算法的博文很好，在此膜拜，Orz...)。事实上在一年前我就接触KMP算法，并尝试用它解决了一些ACM题目，今天写这篇文章就是谈谈我对KMP的理解，让大家对KMP算法有更清楚的认识，希望对读者有帮助。

###算法简介

KMP算法是一种字符串匹配算法，以它的发明者D.E.Knuth，V.R.Pratt，J.H.Morris命名。该算法主要功能是:给定字符串T和P,判断P是否是T的一个子串（关于子串请参照[这里](http://baike.baidu.com/view/3488712.htm?fr=aladdin)）

###朴素算法

朴素的匹配算法就是暴力枚举T的所有子串与P进行比较，容易看出这种方法在最坏情况下复杂度为**O(len(T)*len(P))**,(事实上在实际应用中很难达到这个复杂度，概率还是很小的)。

朴素匹配代码如下<commit_msg>Update 2014-10-06-KMP.md<commit_after>﻿---
layout: post
title: LaTeX beamer制作幻灯片
category: 技术
tags: LaTeX
---


###说明
关于KMP算法，网上资料很多，但讲明白的似乎并不是很多([Matrix67](http://www.matrix67.com/blog/archives/115)大牛那篇关于KMP算法的博文很好，在此膜拜，Orz...)。事实上在一年前我就接触KMP算法，并尝试用它解决了一些ACM题目，今天写这篇文章就是谈谈我对KMP的理解，让大家对KMP算法有更清楚的认识，希望对读者有帮助。

###算法简介

KMP算法是一种字符串匹配算法，以它的发明者D.E.Knuth，V.R.Pratt，J.H.Morris命名。该算法主要功能是:给定字符串T和P,判断P是否是T的一个子串（关于子串请参照[这里](http://baike.baidu.com/view/3488712.htm?fr=aladdin)）

###朴素算法

朴素的匹配算法就是暴力枚举T的所有子串与P进行比较，容易看出这种方法在最坏情况下复杂度为**O(len(T)*len(P))**,(事实上在实际应用中很难达到这个复杂度，概率还是很小的)。

朴素匹配代码如下
{'fraction_non_alphanumeric': 0.1658206429780034, 'fraction_numerical': 0.030456852791878174, 'mean_word_length': 9.198275862068966, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5367552', 'n_tokens_mistral': 934, 'n_tokens_neox': 1014, 'n_words': 36}