1. 数据结构-串的模式匹配
串的模式匹配就是子串定位操作。给定两个串s="s0 s1 ... s(n-1)"和t="t0 t1 ... t(m-1)"（其中n和m分别是串s和t的长度），在主串s中寻找子串t的过程称为模式匹配，t称为模式。如果在s中找到等于t的子串，则称匹配成功，返回t在s中的首次出现的下标位置；否则匹配失败，返回-1。
本文介绍三个串模式匹配算法，分别是简单回溯算法（Brute-Force，BF算法）、KMP算法、KMP算法的改进。
从主串s的第0个字符开始，与模式串t的第0个字符开始逐字符比较，不相同时回溯到模式串t的第0个和主串s的第1个字符，重新开始比较。以此类推，直到t的所有字符完成匹配，则匹配成功，否则匹配失败。
BF算法速度慢的原因是存在大量不必要的回溯，即在某一趟与t的匹配过程失败后，需要返回s串开始字符的下一字符重新开始比较，这对于某些模式串t来说是不必要的。例如，若s=12123123132，t=12313，在t与12 12312 3132中加粗子序列进行比较时，在 2 处发生失配，BF算法接下来将t与121 23123 132、1212 31231 32、12123 12313 2比较。由于t中的231、312与其开始的123并不相同，显然t与121 23123 132、1212 31231 32的比较是不必要的。
KMP算法就是利用模式串中与模式串开头部分子串的重复性来减少重复回溯，实现新一轮比较的直接跳转。 具体来说，KMP算法利用一个数组记录模式串中每一个字符前面有几个字符与模式串从头重复，在与s串比较失配时，直接跳转到重复子串的下一个字符继续比较，而不用跳转至模式串t的第0个字符。
算法步骤： ①计算跳转数组next。②利用KMP算法进行模式匹配。
next数组通过递推计算，即如果当前字符 t[j] 的前一个字符 t[j-1] 与其 next[j-1] 指向的字符 t[next[j-1]] 相同，意味着 t[j] 前的 next[j-1]+1 个字符与从 t[0] 到 t[next[j-1]] 的子串相同，因此 next[j]=next[j-1]+1 ；如果不相同，则递推至 t[next[j-1]] 的next值指向的字符，与 t[j-1] 比较，直到确认 t[j] 前与 t 串从头重复的字符数，或者无重复字符标记为 0 。
注意此处的函数返回参数类型为int*，用于 返回一位数组 ，且返回的这个一位数组必须在函数中用static定义。
KMP算法进行模式匹配时，只需在回溯时将 j 指针赋值为 next[j] 。需要注意的是，若 next[j] 为 -1 ，则意味着 t[j] 前面没有与 t 从头重复的字符，且 t[j] 与 s[i] 失配，则 i 和 j 均加 1 。
考虑更特殊的模式串，还能进一步减少不必要的回溯次数。例如，s=111211112，t=11112，按照上述next的计算方式，next={-1,0,1,2,3}。当 i=3, j=3 时失配，此时 s[i]=2, t[j]=1 ，由于 next[j]=2 ，于是 j 跳转为 2 ，t=11 1 12与s=111 2 11112比较。由于 t[next[j]]=t[j] 也为 1 ，必然与 s[i]=2 不相同，显然这次回溯也不必要。
总结来说， 当失配的字符与待跳转的字符相同时，跳转一步并无意义，可再跳一步 ，即将当前字符置为跳转后字符的next值。
2. 数据结构模式匹配求next值，主串abcaabccacabcabcaaaabc，模式abcabcaaa，怎么求next值，详细通俗点的过程
例如：
1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next值 0 1 1 2 2 3 1 2
next数组的求解方法是：第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。
方法有几种, 我现在只明白了这一种. 还有一种是 前面第一个next值为 -1开始的.
3. 模式匹配 pattern-matching (数据比较)
要理解模式匹配(pattern-matching)，先把这两个单词拆开，先理解什么是 模式(pattern) ，这里所的模式并不是设计模式里的模式，而是数据结构上的，这个模式用于描述一个结构的组成。
我们很容易联想到“ 正则表达”里的模式 ，不错，这个pattern和正则里的pattern相似，不过适用范围更广，可以针对 各种类型的数据结构 ，不像正则表达只是针对字符串。比如正则表达式里"^A.*"这个pattern 表示以A开头、后续一个或多个字符组成的字符串； List("A", _, _*)也是个pattern，表示第一个元素是”A”，后续一个或多个元素的List。
狭义的看，模式可以当作对某个类型，其内部数据在结构上抽象出来的表达式。如上面的List("A", _, _*)就是一种List结构的pattern。模式匹配(pattern-matching)则是匹配变量是否符合这种pattern。比如List("A","B")和List("A","X","Y")就符合上面的pattern，而List("X")则不符合。
例子中的：Array(1,2,3)，List("A",_,"C")等都是模式，表示由指定元素组成的某种类型。
当然模式也不仅仅是表示某种结构的，还可以是常量，或类型，如：
在 scala里对pattern有明确的定义，在形式上有以下几种pattern：
1） 常量模式(constant patterns) 包含常量变量和常量字面量
常量模式和普通的 if 比较两个对象是否相等(equals) 没有区别，并没有感觉到什么威力
2) 变量模式(variable patterns)
确切的说单纯的变量模式没有匹配判断的过程，只是把传入的对象给起了一个新的变量名。
scala> site match { case whateverName => println(whateverName) }
上面把要匹配的 site对象用 whateverName 变量名代替，所以它总会匹配成功。不过这里有个约定，对于变量，要求必须是以小写字母开头，否则会把它对待成一个常量变量，比如上面的whateverName 如果写成 WhateverName 就会去找这个 WhateverName 的变量，如果找到则比较相等性，找不到则出错。
变量模式通常不会单独使用，而是在多种模式组合时使用，比如
List(1,2) match{ case List(x,2) => println(x) }
里面的x就是对匹配到的第一个元素用变量x标记。
3) 通配符模式(wildcard patterns)
通配符用下划线表示："_"，可以理解成一个特殊的变量或占位符。
单纯的通配符模式通常在模式匹配的最后一行出现，case _ =>它可以匹配任何对象，用于处理所有其它匹配不成功的情况。
通配符模式也常和其他模式组合使用：
scala> List(1,2,3) match{ case List(_,_,3) => println("ok") }
上面的List(_,_,3)里用了2个通配符表示第一个和第二个元素，这2个元素可以是任意类型
通配符通常用于代表所不关心的部分，它不像变量模式可以后续的逻辑中使用这个变量。