一、朴素模式匹配


 朴素模式匹配算法


 就是遍历主串，然后把待匹配字符串与子串进行比对，先把待匹配子串的第一个字母与主串进行匹配，若匹配成功，则两串的坐标依次 ++，匹配不成功时，主串坐标返回到开始匹配时的坐标，待匹配串坐标清零，若待匹配坐标等于待匹配子串长度，则证明匹配成功， 返回匹配完毕主串的第一个坐标，否则返回-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).

目录
 
1、图像模式匹配概念
 
2、影响图像模式匹配的因素
 
3、灰度匹配
 
4、几何匹配
 

目录
 
一、基本语法
 
二、模式守卫
 
三、 模式匹配类型
 
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)
 
 

一.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