一、朴素模式匹配
朴素模式匹配算法
就是遍历主串，然后把待匹配字符串与子串进行比对，先把待匹配子串的第一个字母与主串进行匹配，若匹配成功，则两串的坐标依次 ++，匹配不成功时，主串坐标返回到开始匹配时的坐标，待匹配串坐标清零，若待匹配坐标等于待匹配子串长度，则证明匹配成功， 返回匹配完毕主串的第一个坐标，否则返回-1
假设主串的长度为N，待匹配串的长度为M，因为需要遍历主串，每次匹配的长度都小于等于M，所以
  它的时间复杂度是O(M*N)的
	public static int puSu(String str1, String match1) {
		int length1 = str1.length();
		int length2 = match1.length();
		//i，j，k分别表示的是主串下标、匹配串下标、记录下次循环主串开始的位置
		int i = 0;
		int j = 0;
		int k = 0;
		char [] str = str1.toCharArray();
		char [] match = match1.toCharArray();
		while(i < length1 && j < length2) {
			if(str[i] == match[j]) {
				i++;
				j++;
			}else {
				k++;
				j = 0;
				i = k;
			}
		}
		if(j == length2) {
			return k;
		}else {
			return -1;
		}	
	}
	public static void main(String[] args) {
		String str = "asdfghg";
		String m1 = "sd";
		String m2 = "ad";
		System.out.println(puSu(str, m1));
		System.out.println(puSu(str, m2));
	}


二、KMP模式匹配算法
KMP模式匹配算法
因为朴素匹配的时间复杂复杂度为O(M*N)，因此我们寻求一个时间复杂度较小的模式匹配算法，
KMP，一般用来表示克努斯-莫里斯-普拉特算法（Knuth-Morris-Pratt），是在一个“主文本字符串” Str内查找一个“词” Match 的出现，通过观察发现，在不匹配发生的时候这个词自身包含足够的信息来确定下一个匹配将在哪里开始， 以此避免对以前匹配过的字符重新检查。KMP模式匹配算法主要解决的是传统朴素模式匹配算法，当主串从i开始进行匹配，当匹配到j位置时，发现不匹配，主串跳回i+1位置，匹配串跳回0位置，这就导致匹配的效率很低，时间复杂度很高。KMP则当到j位置不匹配时，主串不动，匹配串先通过计算从当前位置的前缀子串和后缀子串的最大匹配串的长度， KMP算法的精髓就是在于求nextArray的过程，这个数组的作用就是把待匹配字符串从头开始向右滑动和主串进行匹配（每次滑动的大小就是nextArray[i]存储的值的大小）从而省去了match字符串返回到终点和主串返回到i+1位置 上的过程。

 逻辑思路：
 ①求nextArray数组的值。我们在进行KMP模式匹配的时候，因为每次匹配失败，match字符串都要向右滑动nextArray[j-i]
个长度的值，所以，第一步就是要求得nextArray数组的值。如何求nextArray的值？首先我们来看nextArray数组的定义：
当主串从i位置开始匹配，到j位置失败的时候，match指针现在的位置是在j-i位置上的，我们得到一个必须一match[0]开头的前缀字符串，必须以match[j-i-1]结尾的后缀字符串，这两个字符串的最大匹配长度就是nextArray[j-i]的值。举个例子：假设match="aaaaabb",这个字符串，匹配失败的时候j-i的值为6，则match[j-i]="b",所以它之前的字符串为 "aaaaab",其前缀字符串为match[1,2,3,4,5]="aaaab",后缀字符为match[0,1,2,3,4]="aaaaa"所以它的最大匹配字符串为"aaaa",长度为4，所以，nextArray[j-i]的值为4.
②当主串从i位置开始匹配的时候，匹配到j位置发现不匹配。如果，此时nextArray的值为-1也就是没有找到滑动的字符串 的时候，主串的位置++，否则，把match的字符串的从头向右滑动nextArray[j-i]个字符，让match[k],k的值为 nextArray[j-i]的值+1，与str[j]的值进行匹配，直至str在某一位置把match匹配完，则证明str中有match 返回的位置为si-mi的值，如果match滑到最后也没有匹配出来，则证明该主串中没有match，返回-1，整个过程结束。
public static int getIndexOf(String s, String m) {
		if(s == null || m == null || m.length() < 1 || s.length() < m.length()) {
			return -1;
		}
		char [] ss = s.toCharArray();
		char [] ms = m.toCharArray();
		int si = 0;
		int mi = 0;
		int [] nextArray  = getNextArray(ms);
		while(si < s.length() && mi < m.length()) {
			if(ss[si] == ms[mi]) {
				si++;
				mi++;
			}else if(nextArray[mi] == -1) {
				si++;
			}else {
				mi = nextArray[mi];
			}
		}
		
		return mi == m.length() ? si - mi : -1;
		
	}
	
	//求nextArray的过程
	public static int[] getNextArray(char[] ms) {
		//当待匹配串不匹配时已匹配串的的长度+1等于1时，由定义可知nextArray==-1
		if(ms.length == 1) {
			return new int [] {-1};
		}
		int [] nextArray = new int [ms.length];
		//由定义可知，nextArray的第一个值和第二个值为-1和0
		nextArray[0] = -1;
		nextArray[1] = 0;
		//匹配失败的位置
		int pos = 2;
		//因为是从头向后进行匹配，所以在算nextArray[j-1]的值得时候nextArray[j-i-1]的值就已经知道了
		//cn代表的值就是最大匹配长度，他的含义是已匹配字符串的前缀字符串的下一个字符串，
		//match[cn]和match[j-i-1]进行比较,若相等，则nextArray[j-i] = nextArray[j-i-1]+1
		//若不相等，则看match[cn]这个字符的最长前缀和后缀匹配情况，也就是求nextArray[cn],
		//求这个数组的长度和上一步一样，看nextArray[cn-1]的值，和两个前缀字符串假设两个区域是n和m，n的下一个
		//字符串的值为x，则判断x的值和match[cn-1]的值是否相等，若相等，则nextArray[j-i] = nextArray[cn]+1
		//不相等则继续进行判断，直至match[cn] <= 0时证明该段字符串的最长匹配值为0，即nextArray[j-i] = 0
		int cn = 0;
		while(pos < ms.length) {
			if(ms[pos] == ms[cn]) {
				nextArray[pos++] = ++cn;
			}else if(cn > 0) {
				cn = nextArray[cn];
			}else {
				nextArray[pos++] = 0;
			}
		}
	
		return nextArray;
	}
	public static void main(String[] args) {
		String str = "asdfghg";
		String m1 = "df";
		String m2 = "ad";
		System.out.println(getIndexOf(str,m1));
		System.out.println(getIndexOf(str, m2));
	}


KMP算法的时间复杂度：
匹配的过程会遍历主串，遍历主串的代价是O(N)的，再来看求nextArray这个方法的时间复杂度，主要是两个量，一个是pos这个变量，它的含义就是匹配失败的坐标，所以大小肯定小于M，再来看pos-cn这个变量，也就是滑动的次数，因为破损最大值为M-1，cn最小值为0，所以pos-cn的值还是小于M的，因此它的时间复杂度不会超过2M,也就是O(M)，所有他的时间复杂度为O(N)+O(M)，因为在实际情况中，M的大小要远小于N的，所以，我们可以把它的时间复杂度看成O(N).

转载请注明出处：http://blog.csdn.net/fightlei/article/details/52712461

 

首先我们需要了解什么是模式匹配？

子串定位运算又称为模式匹配（Pattern Matching）或串匹配（String Matching）。在串匹配中，一般将主串称为目标串，将子串称为模式串。本篇博客统一用S表示目标串，T表示模式串，将从目标串S中查找模式串T的过程称为模式匹配。

虽然我们的主角是KMP模式匹配算法，但我们还是要先从暴力匹配算法讲起，通过发现暴力匹配算法存在的问题，由此来引出KMP模式匹配算法。

 

朴素的模式匹配算法

 

【基本思想】

从目标串S的第一个字符开始和模式串T的第一个字符进行比较，如果相等则进一步比较二者的后继字符，否则从目标串的第二个字符开始再重新与模式串T的第一个字符进行比较，以此类推，直到模式串T与目标串S中的一个子串相等，称为匹配成功，返回T在S中的位置；或者S中不存在值与T相等的子串，称匹配失败，返回-1.此算法也称为BF（Brute-Force）算法。

 

我们先通过一个简单的例子，来了解一下BF算法是怎么回事。假设有一个目标串S为“ababb”，模式串T为“abb”。由于例子比较简单，我们可以绘制出整个的匹配过程。如下图所示：



可以看到匹配流程完全是按照上面给出的基本思想走下来的，首先从目标串S的第一个字符开始和模式串T的第一个字符进行比较（第一趟），如果相等则进一步比较二者的后继字符（第二趟），否则从目标串的第二个字符开始再重新与模式串T的第一个字符进行比较（第三趟，第四趟）。我们重点来关注一下第三趟，此时，发现S[i] != T[j]，则要从目标串S的第二个字符再重新开始，i回溯到i = i - j + 1。因为i - j表示这一趟的起始匹配位置，i - j + 1则意为从这一趟起始比较位置的下一个位置继续进行比较。同时j要回溯到0，即重新与模式串T的第一个字符进行比较。

【BF算法实现】

 

	/*
	 * BF匹配算法
	 */
	public static int violentMatching(String s, String t) {
		int i = 0;
		int j = 0;
		while (i < s.length() && j < t.length()) {
			if (s.charAt(i) == t.charAt(j)) {
				i++;
				j++;
			} else {
				//i回溯到这一趟起始匹配位置的下一个位置
				i = i - j + 1;
				j = 0;
			}
		}
		//当j==t.length()表示目标串S中的一个子串与模式串T完全匹配
		if (j == t.length()) {
			//返回这一趟起始匹配位置，即T在S中的位置
			return i - j;
		} else {
			return -1;
		}
	}

BF算法的实现比较简单，思维方式也很直接，比较容易理解。但是我们发现存在这样的问题：

第一趟比较结束后，我们可以发现信息：S[0] =T[0]，第二趟比较结束后，得到信息：S[1] = T[1]，第三趟后得到信息：S[2] != T[2]。接下来我们通过观察模式串T可以发现T[0] !=T[1]。因此可以立即得出结论T[0] != S[1]，所以根本无需进行第四趟的比较。可能由于例子比较简单，无法鲜明的体现出KMP算法的优势，下面我们举一个稍微复杂些的例子来看看：

假设有一个目标串S为“ababcabcacb”，模式串为“abcac”，当比较到到S[2]与T[2]时出现失配



 

 

 

如果是按照BF算法，则下一趟应从S[1]与T[0]进行比较开始。但是通过上一趟的比较我们是可以发现：S[0] = T[0]，S[1] = T[1]，S[2] != T[2]。再观察模式串T自身我们发现T[0] != T[1]，因此可以立即得出结论S[1] != T[0]，所以可以省略它们的比较，直接从S[2]与T[0]进行比较开始：



从图中可以看到，当比较到S[6]和T[4]时，再次出现失配情况。如果继续按照BF算法，显然又会多进行几次不必要的比较。那么又应该从目标串和模式串的哪两个位置开始进行比较呢？

从上图可以看出比较结束时，有如下信息：S[2] = T[0]，S[3] = T[1]，S[4] = T[2]，S[5] = T[3]，S[6] != T[4]。然后我们在观察模式串T，可以得到：

（1）T[0] != T[1]，因此T[0] != S[3]，所以可以省略它们的比较。

（2）T[0] != T[2]，因此T[0] != S[4]，省略它们的比较。

（3）T[0] = T[3]，因此T[0] = S[5]，当相等时继续比较两个串的后继字符，所以从S[6]和T[1]开始进行比较。



可以看到应用此方法，只发生了三次重新匹配，就得到了匹配成功的结论，加快了匹配的执行速度。

上面的例子只是大概描述了方法的思路，但是这种方法到底是什么，到底如何精确的进行描述，以及如何用代码实现呢？下面就来解决这些问题。

 

KMP模式匹配算法

 

此算法是由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现的，因此该算法被称为克努斯-莫里斯-普拉特操作，简称为KMP算法。

KMP算法，是不需要对目标串S进行回溯的模式匹配算法。读者可以回顾上面的例子，整个过程中完全没有对目标串S进行回溯，而只是对模式串T进行了回溯。通过前面的分析，我们发现这种匹配算法的关键在于当出现失配情况时，应能够决定将模式串T中的哪一个字符与目标串S的失配字符进行比较。所以呢，那三位前辈就通过研究发现，使用模式串T中的哪一个字符进行比较，仅仅依赖于模式串T本身，与目标串S无关。

这里就要引出KMP算法的关键所在next数组，next数组的作用就是当出现失配情况S[i] != T[j]时，next[j]就指示使用T中的以next[j]为下标的字符与S[i]进行比较（注意在KMP算法中，i是永远不会进行回溯的）。还需要说明的是当next[j] = -1时，就表示T中的任何字符都不与S[i]进行比较，下一轮比较从T[0]与S[i+1]开始进行。由此可见KMP算法在进行模式匹配之前需要先求出关于模式串T各个位置上的next函数值。即next[j]，j = 0,1,2,3,...n-1。

 

求解next数组

根据next数组的特性，匹配过程中一旦出现S[i] != T[j]，则用T[next[j]]与S[i]继续进行比较，这就相当于将模式串T向右滑行j - next[j]个位置，示意图如下：



理解上面这幅图是理解next数组的关键，为了绘图简单，使用k 来表示next[j]。图中，j+1表示模式串T的字符个数，当出现失配情况时，使用T[next[j]]与S[i]进行比较，即图中T[k]与S[i]进行比较。因此右边括起来的是T[0]~T[k]共k+1个字符，因此左边括起来的是j + 1 - (k + 1) = j - k个字符，即向右滑行了j-next[j]个位置。

当上图中出现失配后可以得到如下信息：

S[i-j] = T[0]，S[i-j+1] = T[1]，...，S[i-k] = T[j-k]，S[i-k+1] = T[j-k+1]，...，S[i-2] = T[j-2]，S[i-1] = T[j-1]

模式串T进行右滑后，如图中所示必须保证：

S[i-k] = T[0]，S[i-k+1] = T[1]，S[i-k+2] = T[2]，...，S[i-2] = T[k-2]，S[i-1] = T[k-1]

通过上面两个式子可得：

T[0] = T[j-k]，T[1] = T[j-k+1]，T[2] = T[j-k+2]，...，T[k-2] = T[j-2]，T[k-1] = T[j-1]

它的含义表示对于模式串T中的一个子串T[0]~T[j-1]，K的取值需要满足前K个字符构成的子序列（即T[0]~T[k-1]，称为前缀子序列）与后K个字符构成的子序列（即T[j-1]~T[j-k]，称为后缀子序列）相等。满足这个条件的K值有多个，取最大的那个值。

由此求解next数组问题，便被转化成了求解最大前缀后缀子序列问题。

再通过一个例子来说明最大前缀后缀子序列分别是什么？

对于子串“aaabcdbaaa”，满足条件的K值有1,2,3，取最大K值即3做为next[j]的函数值。此时的最大前缀子序列为“aaa”，最大后缀子序列为“aaa”。

再比如子串“abcabca”，其相等的最大前缀后缀子序列即为“abca”

【求解next数组的算法实现】

 

	public static int[] getNext(String t) {
		int[] next = new int[t.length()];
		next[0] = -1;
		int suffix = 0;  // 后缀
		int prefix = -1;  // 前缀
		while (suffix < t.length() - 1) {
			//若前缀索引为-1或相等，则前缀后缀索引均+1
			if (prefix == -1 || t.charAt(prefix) == t.charAt(suffix)) {
				++prefix;
				++suffix;
				next[suffix] = prefix;  //1  
			} else {
				prefix = next[prefix];  //2
			}
		}
		return next;
	}

代码其实并不复杂，整体思路是分别以T[0]~T[suffix]为子串，依次求这些子串的相等的最大前缀后缀子序列，即next[suffix]的值。

 

比较难理解的应该是有两处，我分别用1和2标示了出来。我们依次来看。初始化的过程如下图所示，prefix指向-1，suffix指向0，next[0] = -1。



if条件中prefix = -1成立，所以进入if语句，prefix = prefix+1，suffix = suffix+1，此时直接将next[suffix]赋值为prefix。即next[1] = 0。prefix+1到底代表的是什么？next[suffix]又代表的是什么？

next[suffix]表示的是不包括suffix即T[0]~T[suffix-1]这个子串的相等最长前缀后缀子序列的长度。意思是这个子串前面有next[suffix]个字符，与后面的next[suffix]个字符相等。

代码中suffix+1以后值为1，prefix+1以后值为0，next[1]表示的是对于子串“a”，它的相等最长前缀后缀子序列的长度，即为prefix，0。prefix一直表示的就是对于子串T[0]~T[suffix-1]前面有prefix个字符与后面prefix个字符相等，就是next[suffix]

继续往下走，满足if条件T[0] = T[1]，则suffix+1值为2，prefix+1以后值为1，next[2] = 1，表示子串“aa”，有长度为1的相等最长前缀后缀子序列“a”。

 

继续往下走，满足if条件T[1] = T[2]，则suffix+1值为3，prefix+1以后值为2，next[3] = 2，表示子串“aaa”，有长度为2的相等最长前缀后缀子序列“aa”。

当再继续往下走时会发现T[2] != T[3]，不满足条件，则进入了else语句，prefix进行了回溯，prefix = next[prefix]，这就遇到了第二个难点，为什么要如此进行回溯呢？

借用网上的一张图来回答这个问题



这张图网上很多，但是详细描述这张图的具体含义的却很少。图中的j就对应代码中的suffix，k就对应代码中的prefix，模式串T图中用的P表示。

现在它们也遇到了这个问题，Pj] != P[k]，然后k进行了回溯，变为next[k]。既然prefix能走到k，suffix能走到j，则至少能保证对于子串P[0] ~ P[j-1]，前面有k个字符与后面k个字符相等。即图中前后方的蓝色区域。要是满足条件P[k] = P[j]则说明对于子串P[0] ~ P[j]，前面有k+1个字符与后面k+1个字符相等。但是现在不满足，则说明对于子串P[0] ~ P[j]不存在长度为k+1的相等最长前缀后缀子序列，可能存在比k+1小的最长前缀后缀子序列，可能是k，可能是k-1，k -2 , k -3 ...或者根本就没有是0。那么我们的正常思路应该是回溯到k再进行判断，不存在k个则再回溯到k-1个，以此类推，那么算法中为什么是直接回溯到next[k]呢？



为了便于描述，我将图中的不同区域使用大写字母进行标注。前面说过正常思路是不存在k+1个，就回溯到k个进行判断，现在我们来看为什么不回溯到k？当回溯到k时，需要满足的条件是X区域的字符与Z区域的字符相等，而我们已知的是X区域的字符与Y区域的字符相等，若要满足条件，则需要Y区域字符与Z区域字符相等，从图中可以看到，Y区域与Z区域的字符仅相差一位，实际上比较的是Y区域的第一个字符与第二个字符，第二个字符与第三个字符等等，所以除非是Y区域的字符全部相等，是同一个字符，否则是不可能满足条件的。然而当Y区域的字符全部相等时，则X区域的字符也全部相等，那么next[k]就等于k，所以不如直接就回溯到next[k]。

那为什么直接回溯到next[k]就一定会满足条件呢？

已知的是X区域等于Y区域，所以B区域一定等于D区域，因为B区域表示X区域的后next[k]个字符，D区域表示Y区域的后next[k]个字符。

而next[k]的含义就是对于子串P[0] ~ P[k-1]，前面有next[k]个字符与后面next[k]个字符相等，即A区域等于B区域，所以可以得到A区域一定等于D区域，因此当下次比较满足条件P[next[k]] = P[j]时，就一定有长度为next[k] + 1的相等最长前缀后缀子序列。

next数组的求解搞清楚了，接下来我们就可以给出KMP算法的完整实现了

【KMP模式匹配算法实现】

 

	public static int KMP(String s, String t) {
		int i = 0;
		int j = 0;
		//得到next数组
		int[] next = getNext(t);
		while (i < s.length() && j < t.length()) {
			if (j == -1 || s.charAt(i) == t.charAt(j)) {
				i++;
				j++;
			} else {
				//根据next数组的指示j进行回溯，而i永远不会回溯
				j = next[j];
			}
		}
		if (j == t.length()) {
			return i - j;
		} else {
			return -1;
		}
	}

代码和BF算法很类似，不同的是在进行回溯时，j是根据next[j]进行回溯，i不回溯。

 

 

KMP算法优化

上面给出的KMP算法还有一些小问题，比如有一个模式串“aaaaax”，目标串“aaaabcde”。通过上面给出的算法我们很容易得到模式串T的next数组，匹配过程如下图所示：



可以看到当匹配到S[4]和T[4]时出现失配情况，而根据next数组的指示，next[4]，下一步应该比较S[4]和T[3]，再次失配，再根据指示，比较S[4]和T[2]，再失配，再比较S[4]和T[2]，又失配，直到比较到S[0]和T[0]仍然失配，然后next[0] = -1，则表示T中的任何字符都不与S[4]进行比较，下一轮比较从S[5]与T[0]开始进行。对于这种特殊情况，虽然我们使用了next数组，但效率仍然是低下的。当S[4] != T[4]时，由于T[4] = T[3] = T[2] = T[1] = T[0]，所以它们都不会与S[4]相等，因此应该直接用T[0]与S[5]进行比较。

针对这种情况，只需改进next数组的求解过程即可

【next数组求解算法优化实现】

 

	public static int[] getNext(String t) {
		int[] next = new int[t.length()];
		next[0] = -1;
		int suffix = 0;  // 后缀
		int prefix = -1;  // 前缀
		while (suffix < t.length() - 1) {
			//若相等或前缀索引为-1，则前缀后缀索引均+1
			if (prefix == -1 || t.charAt(prefix) == t.charAt(suffix)) {
				++prefix;
				++suffix;
				//改进的地方
				if (t.charAt(prefix) == t.charAt(suffix)) {
					next[suffix] = next[prefix];
				} else {
					next[suffix] = prefix;
				}
			} else {
				prefix = next[prefix];  
			}
		}
		return next;
	}

改进的地方在于，如果T[suffix] != T[prefix]，则仍然遵从之前的处理，next[suffix] = prefix。

 

若T[suffix] = T[prefix]则可能会出现上面例子所说的特殊情况，使next[suffix] = next[prefix]。其实这就是一个回溯过程，原本应该是next[suffix] = prefix，这里由prefix回溯到了next[prefix]。可以这样理解，当再T[suffix]位置出现失配时，本来按照next数组的指示应采用T[next[suffix]] = T[prefix]进行下一轮比较，但是我们已经得知T[suffix] = T[prefix]所以一定会再次出现失配情况，所以我们下一轮直接使用T[next[prefix]]进行比较。

 

完整的可运行代码可以点击这里查看

 

如有纰漏，敬请海涵。

一.Scala的模式匹配

Scala的模式匹配，比java的功能更加全面，应用比较广泛

Scala中提供本类（case class),对模式匹配进行优化

package day1228

object Demo extends App {

  /**
    * 模式匹配
    * */
  //定义一个变量
  val ch1 = "*"

  //标识符 如果ch1是+，sign=1 如果ch1是-1，sign=-1
  var sign=0

  ch1 match {
    case "+" =>sign=1
    case "-"=>sign= -1
    case _ =>sign
  }
  println(sign)
  println("——————————————————————")

  //2.scala的守卫（case _ =>sign），case _ if
  //匹配所有数组ch2

  var ch2 ='*'
  var digit: Int = -1

  ch2 match {
    case '-'=>println("这是一个减号")
    case '+'=>println("这是一个加号")
      //digit(ch2,10)第一个参数转化的数据，第二个参数多少进制
    case _ if Character.isDigit(ch2) => digit = Character.digit(ch2,8)
    case _=>println("其他")
  }
    println(digit)

  println("_____________________________________________")
  //模式匹配中可以使用变量
  var ch3 ="hello world"
  ch3(6) match {
    case '+'=>println("+")
    case '-'=>println("-")
      //随意定义一个变量，就可以用
    case ch123dacd => println(ch123dacd)

  }
  println("______________________________________________")
//匹配类型
//Andy是任何类型的父类，接收一个子类对象
  var ch4:Any ="jACCKSON"
  ch4 match {
    case x:Int =>println("这是一个整数"+x)
    case y:String =>println("这是一个字符串类型"+y)
    case _ =>println("其他的数据类型")
  }

//模式匹配中可以使用变量

println("__________________")
//数组或是列表的匹配
  var ch5 =Array(1,2,3,4,5)
  ch5 match {
    case Array(0) =>println("这是一个空数组")
    case Array(x,y) => println("数组长度为二"+x+y)
    case Array(x,y,z) => println("数组长度为三"+x+y)
    case Array(x,_*) => println("数组包含多个长度"+ch5.length)   
  }
}


 

结果：

0
——————————————————————
其他
-1
_____________________________________________
w
______________________________________________
这是一个字符串类型jACCKSON
__________________
数组包含多个长度5

Process finished with exit code 0



 

 

                                                                                                                       ————保持饥饿，保持学习

                                                                                                                                             Jackson_MVP

目录

一、基本语法

二、模式守卫

三、 模式匹配类型

3.1 匹配常量

3.2 匹配类型

3.3 匹配数组

3.4 匹配列表

3.5 匹配元组

3.6 匹配对象及样例类

四、 变量声明中的模式匹配

五、 for表达式中的模式匹配

六、 偏函数中的模式匹配(了解)

Scala中的模式匹配类似于Java中的switch语法

int i = 10
switch (i) {
    case 10 :
    System.out.println("10");
    break;

    case 20 :
    System.out.println("20");
    break;

    default :
    System.out.println("other number");
    break;
}

但是scala从语法中补充了更多的功能，所以更加强大。

一、基本语法

模式匹配语法中，采用match关键字声明，每个分支采用case关键字进行声明，当需要匹配时，会从第一个case分支开始，如果匹配成功，那么执行对应的逻辑代码，如果匹配不成功，继续执行下一个分支进行判断。如果所有case都不匹配，那么会执行case _分支，类似于Java中default语句。

object TestMatchCase {
  def main(args: Array[String]): Unit = {

    var a: Int = 10
    var b: Int = 20
    var operator: Char = 'd'

    var result = operator match {
      case '+' => a + b
      case '-' => a - b
      case '*' => a * b
      case '/' => a / b
      case _ => "illegal"
    }
    println(result)
  }
}

1）说明

（1）如果所有case都不匹配，那么会执行case _ 分支，类似于Java中default语句，若此时没有case _ 分支，那么会抛出MatchError。

（2）每个case中，不需要使用break语句，自动中断case。

（3）match case语句可以匹配任何类型，而不只是字面量。

（4）=> 后面的代码块，直到下一个case语句之前的代码是作为一个整体执行，可以使用{}括起来，也可以不括。

二、模式守卫

1）说明

如果想要表达匹配某个范围的数据，就需要在模式匹配中增加条件守卫。

2）案例实操

object TestMatchGuard {
    def main(args: Array[String]): Unit = {

        def abs(x: Int) = x match {

            case i: Int if i >= 0 => i
            case j: Int if j < 0 => -j
            case _ => "type illegal"
        }
        println(abs(-5))
    }
}

三、 模式匹配类型

3.1 匹配常量

1）说明

Scala中，模式匹配可以匹配所有的字面量，包括字符串，字符，数字，布尔值等等。

2）实操

object TestMatchVal {
    def main(args: Array[String]): Unit = {
        println(describe(6))
    }
    def describe(x: Any) = x match {

        case 5 => "Int five"
        case "hello" => "String hello"
        case true => "Boolean true"
        case '+' => "Char +"
    }
}

3.2 匹配类型

1）说明

需要进行类型判断时，可以使用前文所学的isInstanceOf[T]和asInstanceOf[T]，也可使用模式匹配实现同样的功能。

2）案例实操

object TestMatchClass {
    def describe(x: Any) = x match {

        case i: Int => "Int"
        case s: String => "String hello"
        case m: List[_] => "List"
        case c: Array[Int] => "Array[Int]"
        case someThing => "something else " + someThing
    }

    def main(args: Array[String]): Unit = {
        //泛型擦除
        println(describe(List(1, 2, 3, 4, 5)))
 
       //数组例外，可保留泛型
        println(describe(Array(1, 2, 3, 4, 5, 6)))
       println(describe(Array("abc")))
    }
}

3.3 匹配数组

1）说明

       scala模式匹配可以对集合进行精确的匹配，例如匹配只有两个元素的、且第一个元素为0的数组。

2）案例实操

object TestMatchArray {
    def main(args: Array[String]): Unit = {
        for (arr <- Array(Array(0), Array(1, 0), Array(0, 1, 0), Array(1, 1, 0), Array(1, 1, 0, 1), Array("hello", 90))) { // 对一个数组集合进行遍历

            val result = arr match {
                case Array(0) => "0" //匹配Array(0) 这个数组
                case Array(x, y) => x + "," + y //匹配有两个元素的数组，然后将将元素值赋给对应的x,y

                case Array(0, _*) => "以0开头的数组" //匹配以0开头和数组
                case _ => "something else"
            }
            println("result = " + result)
        }
    }
}

3.4 匹配列表

1）方式一

object TestMatchList {
    def main(args: Array[String]): Unit = {
        //list是一个存放List集合的数组
        //请思考，如果要匹配 List(88) 这样的只含有一个元素的列表,并原值返回.应该怎么写
        for (list <- Array(List(0), List(1, 0), List(0, 0, 0), List(1, 0, 0), List(88))) {
            val result = list match {
                case List(0) => "0" //匹配List(0)
                case List(x, y) => x + "," + y //匹配有两个元素的List
                case List(0, _*) => "0 ..."
                case _ => "something else"
            }
            println(result)
        }
    }
}

2）方式二

object TestMatchList {
    def main(args: Array[String]): Unit = {
        val list: List[Int] = List(1, 2, 5, 6, 7)
        list match {
            case first :: second :: rest => println(first + "-" + second + "-" + rest)
            case _ => println("something else")
        }
    }
}

3.5 匹配元组

object TestMatchTuple {
    def main(args: Array[String]): Unit = {
        //对一个元组集合进行遍历
        for (tuple <- Array((0, 1), (1, 0), (1, 1), (1, 0, 2))) {
            val result = tuple match {
                case (0, _) => "0 ..." //是第一个元素是0的元组
                case (y, 0) => "" + y + "0" // 匹配后一个元素是0的对偶元组
                case (a, b) => "" + a + " " + b
                case _ => "something else" //默认
            }
            println(result)
        }
    }
}





扩展案例

object TestGeneric {
  def main(args: Array[String]): Unit = {
    //特殊的模式匹配1   打印元组第一个元素
    for (elem <- Array(("a", 1), ("b", 2), ("c", 3))) {
      println(elem._1)
    }
    for ((word,count) <- Array(("a", 1), ("b", 2), ("c", 3))) {
      println(word)
    }
    for ((word,_) <- Array(("a", 1), ("b", 2), ("c", 3))) {
      println(word)
    }
    for (("a",count) <- Array(("a", 1), ("b", 2), ("c", 3))) {
      println(count)
    }
    println("--------------")
    //特殊的模式匹配2 给元组元素命名
    var (id,name,age): (Int, String, Int) = (100, "zs", 20)
    println((id,name,age))
    println("--------------")
    //特殊的模式匹配3   遍历集合中的元组，给count * 2
    var list: List[(String, Int)] = List(("a", 1), ("b", 2), ("c", 3))
    //println(list.map(t => (t._1, t._2 * 2)))
    println(
      list.map{
        case (word,count)=>(word,count*2)
      }
    )
    var list1 = List(("a", ("a", 1)), ("b", ("b", 2)), ("c", ("c", 3)))
    println(
      list1.map{
        case (groupkey,(word,count))=>(word,count*2)
      }
    )

  }
}



3.6 匹配对象及样例类

1）基本语法

class User(val name: String, val age: Int)
object User{
    def apply(name: String, age: Int): User = new User(name, age)
    def unapply(user: User): Option[(String, Int)] = {
        if (user == null)
            None
        else
            Some(user.name, user.age)
    }
}
object TestMatchUnapply {
    def main(args: Array[String]): Unit = {
        val user: User = User("zhangsan", 11)
        val result = user match {
            case User("zhangsan", 11) => "yes"
            case _ => "no"
        }
        println(result)
    }
}

小结

val user = User("zhangsan",11)，该语句在执行时，实际调用的是User伴生对象中的apply方法，因此不用new关键字就能构造出相应的对象。
	
当将User("zhangsan", 11)写在case后时[case User("zhangsan", 11) => "yes"]，会默认调用unapply方法(对象提取器)，user作为unapply方法的参数，unapply方法将user对象的name和age属性提取出来，与User("zhangsan", 11)中的属性值进行匹配
	
case中对象的unapply方法(提取器)返回Some，且所有属性均一致，才算匹配成功,属性不一致，或返回None，则匹配失败。
	
若只提取对象的一个属性，则提取器为unapply(obj:Obj):Option[T]
      若提取对象的多个属性，则提取器为unapply(obj:Obj):Option[(T1,T2,T3…)]

      若提取对象的可变个属性，则提取器为unapplySeq(obj:Obj):Option[Seq[T]]

2）样例类

       （1）语法：      

  case class Person (name: String, age: Int)

       （2）说明

       1、样例类仍然是类，和普通类相比，只是其自动生成了伴生对象，并且伴生对象中自动提供了一些常用的方法，如apply、unapply、toString、equals、hashCode和copy。

       2、样例类是为模式匹配而优化的类，因为其默认提供了unapply方法，因此，样例类可以直接使用模式匹配，而无需自己实现unapply方法。

       3、构造器中的每一个参数都成为val，除非它被显式地声明为var（不建议这样做）

（3）实操

上述匹配对象的案例使用样例类会节省大量代码

case class User(name: String, age: Int)
object TestMatchUnapply {
    def main(args: Array[String]): Unit = {
        val user: User = User("zhangsan", 11)
        val result = user match {
            case User("zhangsan", 11) => "yes"
            case _ => "no"
        }
        println(result)
    }
}

四、 变量声明中的模式匹配

case class Person(name: String, age: Int)
object TestMatchVariable {
    def main(args: Array[String]): Unit = {

        val (x, y) = (1, 2)
        println(s"x=$x,y=$y")
        val Array(first, second, _*) = Array(1, 7, 2, 9)
        println(s"first=$first,second=$second")

        val Person(name, age) = Person1("zhangsan", 16)
        println(s"name=$name,age=$age")
    }
}

五、 for表达式中的模式匹配

object TestMatchFor {
    def main(args: Array[String]): Unit = {
        val map = Map("A" -> 1, "B" -> 0, "C" -> 3)
        for ((k, v) <- map) { //直接将map中的k-v遍历出来
            println(k + " -> " + v) //3个
        }
        println("----------------------")

        //遍历value=0的 k-v ,如果v不是0,过滤
        for ((k, 0) <- map) {
            println(k + " --> " + 0) // B->0
        }
        println("----------------------")

       //if v == 0 是一个过滤的条件
        for ((k, v) <- map if v >= 1) {
            println(k + " ---> " + v) // A->1 和 c->33
        }
    }
}

六、 偏函数中的模式匹配(了解)

偏函数也是函数的一种，通过偏函数我们可以方便的对输入参数做更精确的检查。例如该偏函数的输入类型为List[Int]，而我们需要的是第一个元素是0的集合，这就是通过模式匹配实现的。

偏函数定义
val second: PartialFunction[List[Int], Option[Int]] = {
    case x :: y :: _ => Some(y)
}

                         

注：该偏函数的功能是返回输入的List集合的第二个元素

2）偏函数原理

上述代码会被scala编译器翻译成以下代码，与普通函数相比，只是多了一个用于参数检查的函数——isDefinedAt，其返回值类型为Boolean。

val second = new PartialFunction[List[Int], Option[Int]] {
    //检查输入参数是否合格
    override def isDefinedAt(list: List[Int]): Boolean = list match {
        case x :: y :: _ => true
        case _ => false
    }
    //执行函数逻辑
    override def apply(list: List[Int]): Option[Int] = list match {
        case x :: y :: _ => Some(y)
    }
}

3）偏函数使用

偏函数不能像second(List(1,2,3))这样直接使用，因为这样会直接调用apply方法，而应该调用applyOrElse方法，如下

second.applyOrElse(List(1,2,3), (_: List[Int]) => None)

applyOrElse方法的逻辑为 if (ifDefinedAt(list)) apply(list) else default。如果输入参数满足条件，即isDefinedAt返回true，则执行apply方法，否则执行defalut方法，default方法为参数不满足要求的处理逻辑。

案例实操
（1）需求

将该List(1,2,3,4,5,6,"test")中的Int类型的元素加一，并去掉字符串。

def main(args: Array[String]): Unit = {
  val list = List(1,2,3,4,5,6,"test")
  val list1 = list.map {
    a =>
      a match {
        case i: Int => i + 1
        case s: String =>s + 1
      }
  }
  println(list1.filter(a=>a.isInstanceOf[Int]))
}


（2）实操

方法一：

List(1,2,3,4,5,6,"test").filter(_.isInstanceOf[Int]).map(_.asInstanceOf[Int] + 1).foreach(println)

方法二：

List(1, 2, 3, 4, 5, 6, "test").collect { case x: Int => x + 1 }.foreach(println)