模式匹配_模式匹配算法 - CSDN
  • 模式匹配算法

    2017-09-18 16:24:50
    串的模式匹配设有两个字符串S和T,设S 为主串,设T为子串。在主串S中查找与模式T相匹配的子串,如果匹配成功,确定相匹配的子串中的第一个字符在主串S中出现的位置。 一、 BF算法: 1. 指针i和j 分别指示主串S 和...

    串的模式匹配设有两个字符串S和T,设S 为主串,设T为子串。在主串S中查找与模式T相匹配的子串,如果匹配成功,确定相匹配的子串中的第一个字符在主串S中出现的位置。
    一、 BF算法:
    1. 指针i和j 分别指示主串S 和模式串T 中当前待比较的字符位置,i 和j初始值为1;
    2. 取k来代替i从当前位置开始与j相匹配,此时的i用来记录它本来的值 而k是要随着j的变化而变化的
    3. 遇到不匹配的情况时,从i的下一位开始与j进行再一次的比较
    这种方法简单易理解易实现 但是过于冗余 复杂度较高

    #include <iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    int main()//BF算法,从主串的第一位开始 主串与模式串比较,不匹配时主串的指针要回去从下一位开始匹配
    {
        int i,j,k,ans=-1;
        char S[1001],T[1001];
        scanf("%s%s",&S,&T);
        int lens,lent;
        lens=strlen(S);//主串的长度
        lent=strlen(T);//子串的长度
        for(int i=0;i<lens;++i){//从下一位重新开始匹配
            for(j=0,k=i;j<lent&&k<lens;++j){
                if(S[k]==T[j])
                    ++k;
                else//也即 此时不匹配跳出匹配过程
                    break;
            }
            if(j==lent){
                ans=i;
                break;
            }
        }
        printf("%d\n",ans);//输出开始位置 -1为未匹配成功
        return 0;//此方法虽然能够找到答案,但是时间复杂度很高 重复的过程很多即很慢
    }

    二、KMP
    上面的BF算法 不如说 在S串中找到位置k 从k开始与T匹配 之前 需要遍历S从0到k 而kmp算法所做的工作就是让我们不必从0到k一步一步都遍历一遍 而是跳着匹配 这就要求我们在遇到不匹配的情况时需要知道下一步跳到哪里开始重新匹配 也就是kmp中的next数组了。例如S 串为:ababcabcacbab T串为:abaca
    这里写图片描述

    而所谓的 合适的 位置是如何得来的呢
    现在假设应与T串中的第k个字符继续比较 例如上图第二次匹配,则T串的从1到k-1个字符应该是与S串的从(此时的i是此次匹配开始值i=8)i-k+1到i-1个字符相匹配的,而在第一次匹配过程中可以发现,S串的从(i=8, j=8)i-k+1到i-1个字符是与T串中j-k+1到j-1个字符是匹配的,所以第二次开始时跳到k=4是因为
    T串的从1到k-1个字符 和T串的从j-k+1到j-1个字符相匹配(j=8)
    也就是说kmp基于的是模式串即T串本身的一种 轮回?现在就是在基于模式串来求next数组,以发生不匹配时可以跳到合适的位置
    当j=1时next[j]=0
    next[j]=Max{ k| 1< k < j && T1…..Tk=Tj-k+1……Tj-1}即寻找最大的轮回
    当k=1时 也就是没有所谓的轮回时next[j]=1
    在匹配过程中 若Si==Tj 或者j==0则 i j 都自增1 否则 j 跳到next[j]位置
    然后就是求next数组了 由next数组的定义可知next[1]=0
    假设next[j]=k 这表示在T串中 T1…..Tk-1 = Tj-k+1……Tj-1
    讨论next[j+1]的值 当Tk==Tj 时 显然 next[j+1]=k+1;不等时 仔细想一下 这个过程是不是刚好是串的模式匹配过程 不过这里主串和模式串都是T串 不等时把身为模式串的T串右移 右移到哪呢 到next[k]啊(这里可以拿纸笔自己演算) 默认的存在 k < j 所以此时next[k]是已知条件 这时若Tj==Tnext[k] 则 next[j+1]=next[k]+1 不等就继续找啊 类似dfs一层一层往下找 直到Tj!=T1 此时next[j+1]=1(最好的理解方式就是拿纸笔从头到尾自己演算一遍 不省略任何一个步骤)
    ok 这里说明一下 由于本人偷懒 简陋的代码里字符串是从0开始存的 next[0]=-1 中心思想是没变的

    #include <iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int main()
    {
        int next[1001];
        char S[1001],T[1001];
        scanf("%s%s",&S,&T);
        int lens=strlen(S);
        int lent=strlen(T);
        int i=0,j=-1,ans=-1;
        next[i]=j;
        while(i<lent){
            if(j==-1||T[i]==T[j]){
                ++i;
                ++j;
                //if(T[i]!=T[j])
                    next[i]=j;
                //else
                    //next[i]=next[j];
            }
            else
                j=next[j];
        }
        i=0,j=0;
        while(i<lens){
            if(j==-1||S[i]==T[j]){
                ++i;
                ++j;
            }
            else
                j=next[j];
            if(j==lent){
                ans=i-j;
                break;
            }
        }
        printf("%d\n",ans);//此答案为从0开始计数。。。
        return 0;
    }

    最后讲一下求nextval数组 可以发现 代码中注释掉的部分 添上就是求nextval数组了
    这里发现一件很有意思的事情 之前求next数组时 next[j]=k 求next[j+1]值时第一种情况就是Tj==Tk 现在讨论这种情况下 主串S和模式串T匹配过程中刚好到 j 这个位置失配了 此时 由next[j]=k 就要跳到 k 这个位置进行比较了 可是Tj==Tk啊 不用比较就知道不匹配啊 可是前面求的时候就这样求的 错了吗 没啊 前面没错 这里也没错 可是怎么就不一样了呢 因为前面是根据这两个求的是next[j+1]的值啊 讨论的是j+1不匹配的时候跳到哪里 这里是j不匹配跳到哪里 ok 清楚就行
    nextval数组处理的就是上面这种情况 减去无谓的匹配 这也就有了代码中的注释部分
    最后 此篇文章借鉴于严蔚敏等主编的数据结构(C语言版)课本 有错欢迎指出 谢谢
        

    展开全文
  • 模式匹配Pattern Matching

    千次阅读 2018-12-13 17:45:42
    1.模式匹配(pattern matching)的概念 2. 制造模式匹配的测试串 3. 模式匹配蛮力算法(Brute-Force,也成Naive朴素算法) 3.1 Version 1 3.2 Version 2:(与Version 1的不同在于i,j) 3.3 算法分析 (1)最差...

    目录

     

    1.模式匹配(pattern matching)的概念

    2. 制造模式匹配的测试串

    3. 模式匹配蛮力算法(Brute-Force,也成Naive朴素算法)

    3.1 Version 1

    3.2 Version 2:(与Version 1的不同在于i,j)

    3.3 算法分析

    (1)最差情况

    (2)最佳情况 —— 找到

    (3)最佳情况 —— 没找到

    4. 模式匹配KMP算法

    5. 模式匹配BC(Begin With The End)算法


    1.模式匹配(pattern matching)的概念

    ——一个目标对象 T(字符串)
    ——(pattern)P(字符串)
    在目标 T 中寻找一个给定的模式P的过程

    应用
    1. 文本编辑时的特定词、句的查找
           •UNIX/Linux: sed, awk, grep
    2. DNA 信息的提取

    2. 制造模式匹配的测试串

    制造模式匹配测试串的两种策略

    策略一:随机生成Test串,随机生成Pattern串,然后进行匹配。该策略下,P在T中出现的概率小。

    策略二:随机生成Test串,在从中随机截取Pattern串。

    3. 模式匹配蛮力算法(Brute-Force,也成Naive朴素算法)

    3.1 Version 1

    匹配过程详解:

    T = pepeople

    P = people

    ---------------------------------------

    i = 0    j = 0

    T = pepeople

    P = people

    T[0] = P[0] = p

    i + 1 = 1

    j + 1 = 1

    -----------------------------------------

    i = 1    j = 1

    T = pepeople

    P = people

    T[1] = P[1] = e

    i + 1 = 2

    j + 1 = 2

    ----------------------------------------------

    i = 2    j = 2

    T = pepeople

    P = people

    T[2] = p

    P[2] = 0

    T[2] != P[2]

    i = 2 - (2 - 1) = 1 (T回退)

    j = 0 (P复位)

    ------------------------------------------------

    i = 1    j = 0

    T = pepeople

    P =   people

    (......)

    3.2 Version 2:(与Version 1的不同在于i,j)

    匹配过程详解:

    T = pepeople

    P = people

    ---------------------------------------

    i = 0    j = 0

    T = pepeople

    P = people

    T[0+0]

    T[0] = P[0] = p

    j + 1 = 1

    -----------------------------------------

    i = 0    j = 1

    T = pepeople

    P = people

    T[0+1]

    T[1] = P[1] = e

    j + 1 = 2

    ----------------------------------------------

    i = 0    j = 2

    T = pepeople

    P = people

    T[0+2]

    T[2] = p

    P[2] = 0

    T[2] != P[2]

    i = i+1 = 1

    j = 0 

    ------------------------------------------------

    i = 1    j = 0

    T = pepeople

    P =   people

    T[1+0]

    T[1] = e

    P[0] = p

    (......)

    3.3 算法分析

    3.3.1 最差情况

    3.3.2 最佳情况 —— 找到

    3.3.3 最佳情况 —— 没找到

    4. 模式匹配KMP算法

    推荐JULY的博文:https://blog.csdn.net/v_JULY_v/article/details/7041827

    推荐阮一峰的博文http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

    字符串:BBC  ABCDAB  ABCDABCDABDE

    搜索词:ABCDABD

    1.

    B与A不匹配,搜索词后移一位。

    2.

    B与A不匹配,搜索词再往后移。

    3.

    直到字符串有一个字符,与搜索词的第一个字符相同为止。

    4.

    接着比较字符串和搜索词的下一个字符,还是相同。

    5.

    直到字符串有一个字符,与搜索词对应的字符不相同为止。

    6.

    这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。

    7.

    一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。

    8.

    怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

    9.

    已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。查表可知,最后一个匹配字符B对应的"部分匹配值"为2,因此按照下面的公式算出向后移动的位数:

      移动位数 = 已匹配的字符数 - 对应的部分匹配值(搜索词"前缀"和"后缀"的最长的共有元素的长度)

    因为 6 - 2 等于4,所以将搜索词向后移动4位。

    10.

    因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移2位。

    11.

    因为空格与A不匹配,继续后移一位。

    12.

    逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 - 2,继续将搜索词向后移动4位。

    13.

    逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索词向后移动7位,这里就不再重复了。

    14.

    下面介绍《部分匹配表》是如何产生的。

    首先,要了解两个概念:"前缀"和"后缀"。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。

    15.

    "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,

                                      前缀                                                                      后缀                                              公有元素的长度

        "A"                       空集                                                                    空集                                                                        0

        "AB"                     [A]                                                                         [B]                                                                        0

      "ABC"                 [A, AB]                                                                 [BC, C]                                                                   0

      "ABCD"              [A, AB, ABC]                                                       [BCD, CD, D]                                                          0

      "ABCDA"            [A, AB, ABC, ABCD]                                         [BCDA, CDA, DA, A]                                                1

      "ABCDAB"         [A, AB, ABC, ABCD, ABCDA]                         [BCDAB, CDAB, DAB, AB, B]                                    2

      "ABCDABD"      [A, AB, ABC, ABCD, ABCDA, ABCDAB]      [BCDABD, CDABD, DABD, ABD, BD, D]                      0

    16.

    "部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。

    17. next数组

    next 数组相当于“最大长度值” 整体向右移动一位,然后初始值赋为-1

    移动位数  =  失配字符所在位置(下标从0开始)  -  失配字符对应的next 值

    18 next数组优化版

    相等,则让next[j] = next[k]

    j=3,k=0,next[0]=-1

    j=5,k=1,next[1]=0

    j=7,k=1,next[1]=0

    j=8,k=2,next[2]=0

    5. 模式匹配BC(Begin With The End)算法

    推荐阮一峰的博文:http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

    展开全文
  • 模式匹配

    2019-01-16 16:09:39
    模式匹配 Scala 中的模式匹配类似于java中的 switch 语法, 但是更加强大 模式匹配语法中, 使用 match关键字声明, 每个分支采用 case 关键字进行声明, 当需要匹配是,会在第一个case 分支开始,如果匹配成功,那么执行...

    模式匹配

    Scala 中的模式匹配类似于java中的 switch 语法, 但是更加强大

    模式匹配语法中, 使用 match关键字声明, 每个分支采用 case 关键字进行声明, 当需要匹配是,会在第一个case 分支开始,如果匹配成功,那么执行对应的逻辑代码,如果匹配不成功,继续执行下一个分支进行判断.

    如果所有 case 都不匹配, 那么会执行 case _ 分支, 类似于 java 中的 default语句

    1.1基本应用

    ex1: 输入1,2,3 会打印对应的颜色

    object Color {
    
        def main(args: Array[String]): Unit = {
            //从键盘获取数字
            val i: Int = StdIn.readInt()
            i match {
                case 1 => println("red")
                case 2=> println("green")
                case 3=> println("yellow")
                case _=> println("您的输入有误")
            }
        }
    
    }
    

    说明:

    • 如果所有case都不匹配,那么会执行case _ 分支,类似于 Java 中default语句
    • 如果所有case都不匹配,又没有写case _ 分支,那么会抛出异常
    • 每个case中,不用break语句,自动中断case
    • 可以在match中使用其它类型(任意类型),而不仅仅是字符
    • => 等价于 java swtich:
    • =>后面的代码块到下一个 case, 是作为一个整体执行,可以使用{} 扩起来,也可以不括

    ex2 : 加减乘除

    object MatchDemo2 {
      def main(args: Array[String]): Unit = {
        var a1 = 10
        var a2 = 20
    
        var operChar = "*"
        val res = operChar match {
          case "+" => a1 + a2
          case "-" => a1 - a2
          case "*" => a1 * a2
          case "/" => a1 / a2
          case _ => "你的运算符负不正确"
        }
        println("res = " + res)
      }
    }
    

    1.2 守卫

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

    object MatchDemo3 {
      def main(args: Array[String]): Unit = {
        for (ch <- "+-3&%") {
          var digit = 0
          val sign = ch match {
            case '+' => 1
            case '-' => -1
            case _ if Character.isDigit(ch) => digit = Character.digit(ch, 10)
            case _ => 0
          }
          println("ch = " + ch)
          println("sign = " + sign)
          println("digit = " + digit)
          println("---------")
        }
      }
    }
    

    1.3 变量和常量

    如果在case关键字后跟变量名,那么 match 前表达式的值会赋值给那个变量

    object MatchVar {
    
        def main(args: Array[String]): Unit = {
            var ch = 0
    
            'z' match {
                case 'a' => println("a...")
                case 'b' => println("b...")
                case 'c' => println("c...")
                case ch => println("ch=" + ch)
            }
        }
    }
    

    注意

    • 如果 case ch 匹配成功了, 后面即使跟上case _ 也没有用
    • 可以把case _ 看成 case 变量名 的特例 , 把_看成一个变量来对待

    但是:

    按照约定, Scala 期望模式变量名都以小写字母开头, 而常量名则是大写字母(只要首字母大写也可以)。

    如果你使用大写字母的名称,Scala 将会在作用域范围内查找常量。

    但是,如果使用的是非大写字母的名称,它将只假设其是一个模式变量—-在作用域范围内任何具有相同非大写字母的名称都将会被忽略。

    在下面的代码中,我们定义了一个和字段具有相同名称的模式变量, 但是这段代码将不会给出我们想要的结果—–模式变量隐藏了(Sample 类的)max 字段。

    object PatternTest {
        def main(args: Array[String]): Unit = {
            val sample = new Sample
            sample.process(1000)
        }
    }
    
    class Sample {
        val max = 10000
        def process(input: Int): Unit = {
    
            input match {
                case max => println(s"You matched max")
            }
        }
    }
    

    说明:

    • 你会发现 scala 把 max推断为模式变量, 而不是模式常量.

    • 解决办法:

      • 办法1: 明确指定作用域:this.max

      • 办法2: 使用反引号类给 scala 提示.

         case `max` => .....
        
      • 办法3: 把max变成大写: MAX

    1.4 模式匹配

    object MatchType {
    
        def main(args: Array[String]): Unit = {
    
            val list = List(1, 3.2, "sa",true)
    
            var result = list match {
                case a: List[Int] => println("...Int类型...")
                case b : List[String] => println("...string...")
                case c :List[Double] =>println("...double...")
                case d:List[Boolean] => println("...boolean...")
    
            }
            println(result)
        }
    }
    

    说明:

    • 在进行类型匹配时,编译器会预先检测是否有可能的匹配,如果没有则报错
    • 如果类型匹配成功之后会把s的值赋值给case后面跟着的变量, 而不需要做类型的转换.
    • 对数组来说提供数组元素中的类型是必要的,因为数组的底层类型确实是确定的.比如:Array[Int]这里的Int是必须的
    • 但是对集合类型比如 Map, 提供泛型类型是无用的. 因为 Java 的"泛型擦除". Map[Int, String]和Map[Int, Int] 在匹配的时候没有区别. 所以应该使用通用的泛型:Map[_, _]
    import scala.io.StdIn
    
    object MatchType {
      def main(args: Array[String]): Unit = {
        var s: Any = Map("a" -> 11, "b" -> 22)
    
        var result = s match {
          case d: Map[_, _] => "匹配到的是Map"
          case _ => "啥都没有匹配到"
    
        }
        println(result)
      }
    }
    

    1.5 匹配数组

    object PatternDemo5 {
        def main(args: Array[String]): Unit = {
            // Array(1,2,3) == Array(1,2,3)
            var arr1 = Array(1, 2, 3, 5, 6)
            
            arr1 match {
                //匹配三个元素,只能是三个元素,且为123
                //            case Array(1, 2, 3) => println("Array(1,2,3)")
                
                //匹配四个元素,且前两个元素为1,2
                //            case Array(1, 2, _, _) => println("Array(1,2,_,_)")
                
                //匹配四个元素,第三个元素用变量接收
                //            case Array(1, 2, a, _) => println("Array(1,2,_,_)  " + a)
                
                //匹配前两个元素为1,2,后面是什么都行
                //            case Array(1, 2, _*) => println("Array(1,2, _*)  ")
                
                //匹配前两个为1,2,  后面为一个数组
                // 在未来 @ 会变成 :
                //            case Array(1, 2, rest@_*) => println("Array(1,2, rest@_*)  " + rest.mkString(", "))
                case Array(_, _, rest@_*) => println("Array(_,_, rest@_*)  " + rest.mkString(", "))
                case _ => println("no ")
                
            }
            
        }
    }
    

    1.6 匹配列表

    def main(args: Array[String]): Unit = {
        val arr: List[Int] = List(1, 2, 3, 5, 6)
        val res = arr match {
          //case List(1, 2) => "List(1, 2)"
          //case List(1, _*) => "匹配以 1 开头的列表"
          //case 1 :: 2 :: 3 :: Nil => "匹配List(1,2,3)"
          case 1 :: abc => println(abc); "匹配以 1 开头的列表"
          case _ => "啥也可没有匹配到"
        }
        println(res)
      }
    

    1.7 匹配元组

    object MatchTouple {
    
        def main(args: Array[String]): Unit = {
    
    //        val tup1:(Int , String)= (1,"niefeng")
            val tup2:(Int , String , String)= (2,"bujingyun","chuchu")
    
            tup2 match {
                case (a,b,c) => println(s"a=$a,b=$b,c=$c")
            }
        }
    }
    

    1.8 对象匹配(提取器)

    对象匹配,什么才算是匹配呢?,规则如下:

    1. case中对象的unapply方法(提取器)返回some集合则为匹配成功
    2. 返回None集合则为匹配失败

    备注:

    1. SomeNone 都是Option的子类型
    2. 2.11.1 开始, scala 为了性能上的优势, 放松了对unapply返回的值的类型的限制(不必必须是 Option). 返回的类型只要具有以下方法就可以:
      • def isEmpty: Boolean
        返回值: true用来标记匹配成功, false匹配失败
      • def get: T 返回值: 表示提取到的值.
    3. 其实SomeNone 均包含上面的两个方法.
    4. 另外一种情况: 如果unapply返回一个Boolean值, 则只表示匹配成功或者失败. 如果是 true则表示匹配成功, 但是不会提取到任意的值.
    5. 不过, 大部分情况下, 我们还是把要提取的数据封装到Some中返回.

    1. 提取单个对象

    object MatchObj {
    
        def main(args: Array[String]): Unit = {
            val num = 100.0
    
            num match {
                case Square(z) => println("z =" +z)
            }
        }
    }
    object Square{
        def apply(a:Double): Double = a * a
    
        def unapply(arg: Double): Option[Double] = Some(math.sqrt(arg))
    }
    
    
    result: 10.0
    
    

    执行流程说明:

    1. case匹配的过程中, 如果碰到这种(伴生对象(参数))的形式的时, 就会调用这个伴生对象的unapply方法, 来提前对象.
    2. 调用unapply的时候, 会把前面的匹配表达式(本例中的num)传递给unapply
    3. 如果unapply返回的是Some, 则表示匹配成功. 并unapply的返回值赋值给伴生对象(参数)中的参数(本例中的z), z其实就是提取到的对象
    4. 如果unapply返回的None, 则表示匹配失败.
    5. 继续下一个case的匹配…

    2. 提取多个对象

    object MatchObjs {
    
        def main(args: Array[String]): Unit = {
            val s = "yangguo,xiaolongnv"
            val res = s match {
                case Names(one,two) => println(s"成功! one =$one,two =$two")
                case _ => println("匹配失败")
    
            }
        }
    }
    
    object  Names{
        def unapplySeq(str:String)={
            if (str.contains(","))
                Some(str.split(","))
            else
                None
        }
    }
    

    在这里插入图片描述

    执行过程说明:

    1. case Names(one, two), 这里有 32个需要提取的结果, 所以会调用伴生对象.unapplySeq方法.
    2. 如果这个方法返回的是Some, 并且 Some中的序列有 2个值, 则匹配成功. 否则就匹配失败.

    1.9 变量声明中的模式

    在声明变量的时候,也可以使用模式匹配的方式. (在其他语言中叫做解构)

    object VarMatch {
      def main(args: Array[String]): Unit = {
        var (a: Int, b: Int) = (10, 20)
        println(s"a = $a, b=$b")
    
        val (aa, bb) = BigInt(10) /% 3
        println(s"aa = $aa, bb = $bb")
    
        val arr = Array(100, 200, 300, 400)
        val Array(c, _, d, _*) = arr  //
        println(s"c = $c, d = $d")
      }
    }
    

    在这里插入图片描述

    1.10 for表达式中的模式

    def main(args: Array[String]): Unit = {
        val map = Map("a" -> 1, "b" -> 2, "c" -> 3, "d" -> 2)
    
        // 直接将Map中的K-V遍历出来
        for ((k, v) <- map) {
          println(s"k = $k, v = $v")
        }
        println("--------------")
        // 只遍历 v = 2的 k-v
        for((k, 2) <- map) {
          println(s"k = $k")
        }
        println("--------------")
        // 也可以使用 守卫: 遍历v > 1的
        for ((k, v) <- map if v > 1){
          println(s"k = $k, v = $v")
        }
      }
    

    1.11 样例类

    案例1

    object CaseClassDemo1 {
      def main(args: Array[String]): Unit = {
        val arr = Array(Dollar(1000), Currency(10000, "RMB"))
    
        for (ele <- arr) {
          val res = ele match {
            case Dollar(v) => "$" + v
            case Currency(v, u) => v + u
            case _ => ""
          }
          println(res)
        }
      }
    }
    
    // 一个抽象类
    abstract class Amount {}
    
    // Dollar: 样例类 继承自 Amount
    case class Dollar(value: Double) extends Amount {}
    
    // Currency: 样例类
    case class Currency(value: Double, unit: String) {}
    

    在这里插入图片描述

    案例2

    copy会创建一个与现有对象值相同的新对象,并可以通过带名参数来修改某些属性。

    object CaseClassDemo2 {
      def main(args: Array[String]): Unit = {
        val amt1: Currency = Currency(122.2, "美元")
        // 复制一个与 amt1 完全相同的对象
        val amt2: Currency = amt1.copy()
        val amt3: Currency = amt1.copy(value = 222.2)
        val amt4: Currency = amt1.copy(unit = "英镑")
        println(amt1)
        println(amt2)
        println(amt3)
        println(amt4)
      }
    }
    

    在这里插入图片描述

    案例3

    在这里插入图片描述

    1.12 case语句中的中置表示法

    ![](W:\博客\博客图片\2019-01-16_153746.png)

    1.13 匹配嵌套结构

    object MatchNest {
      def main(args: Array[String]): Unit = {
        val book1 = Book("九阳真经", 100)
        val book2 = Book("葵花宝典", 120)
        val bundle1 = Bundle("书籍", 20, book1, book2)
    
        println(price2(book1))
        println(price2(book2))
        println(price2(bundle1))
    
      }
    
      /**
        * 计算打包的销售的书的价格
        *
        * 方式1:
        */
      def price(item: Item): Double = {
        val money = item match {
          case Book(_, price) => price
          case Bundle(_, discount, items@_*) => {
            var sum = -discount
            for (elem <- items) {
              sum += price(elem)
            }
            sum
          }
          case _ => 0
        }
        money
      }
      // 方式2
      def price2(item: Item): Double = {
        item match {
          case Book(_, price) => price
          case Bundle(_, discount, items@_*) => {
            // 不用循环
            // 把每本书的价格映射到新的序列中, 然后再求和
            items.map(price2).sum - discount
          }
          case _ => 0
        }
      }
    }
    
    // 抽象类
    abstract class Item
    
    // 样式类 Book
    case class Book(description: String, price: Double) extends Item
    
    // 捆绑的样式类
    case class Bundle(description: String, discount: Double, item: Item*) extends Item
    

    1.4 密封类

    package com.liuser.scala.note
    
    object MatchSeal {
    
        def main(args: Array[String]): Unit = {
            val amounts = Array(Dollar1(100),Dollar1(200), new Currency1(100,"rmb"))
    
            for (elem <- amounts) {
                elem match {
                    case Dollar1(v) => println("values=" + v)
                    case Currency1(v,u)=>println("v=" +v ,"u="+u)
                    case _ => println("匹配失败")
                }
            }
    
        }
    }
    //密封类
    sealed abstract class Amount1{}
    
    case class Dollar1(value:Double) extends Amount1{}
    
    case class Currency1(value:Double,unit : String) extends Amount1{}
    

    1.5 模拟枚举类

    object EnumDemo {
      def main(args: Array[String]): Unit = {
        val seasons = Array(Spring, Summer, Autumn, Winter)
        for (season <- seasons) {
          val msg = season match {
            case Spring => "春天"
            case Summer => "夏天"
            case Autumn => "秋天"
            case Winter => "冬天"
            case _ => "每在地球上"
          }
          println(msg)
        }
      }
    }
    
    sealed abstract class Season
    
    case object Spring extends Season
    
    case object Autumn extends Season
    
    case object Summer extends Season
    
    case object Winter extends Season
    
    展开全文
  • 一般的字符串模式匹配算法是类似下面的逐次匹配,举例说明如下 主串s=ababcabcacbab 从串t=abcac 一般匹配方法如下图所示 代码如下 int index(string s,string t) {  int i=0,j=0;  int l1=s.length();  ...

    一般的字符串模式匹配算法是类似下面的逐次匹配,举例说明如下

    主串s=ababcabcacbab

    从串t=abcac

    一般匹配方法如下图所示

    图片

    代码如下

    int index(string s,string t)
    {
        int i=0,j=0;
        int l1=s.length();
        int l2=t.length();
        while(i<=l1-1&&j<=l2-1)
        {
            if(s[i]==t[j])
            {
                ++i;
                ++j;
            }
            else
            {
                if(j==0)
                {
                    ++i;
                }
                else
                {
                    i=i-j+2;
                    j=0;
                }

            }
            //cout<<"i="<<i<<"j="<<j<<endl;
        }
        if(j>l2-1) return i-l2;
        else return 0;
    }

    这样算下来的时间复杂度是O(l1*l2),因为每次只要中间发生字符串s[i]和t[j]不相等,这种算法会把字符串t的索引置为0,而主串s也是从之前开始匹配的i加一个1,其实我们可以发现,中间有些比较是不必要的,比如从第三趟比较就可以看出主串中第4,5,8个字符串是‘b’,'c','a',(对应模式串中的第2,3,4个字符)。而模式串t中第一个字符是a,所以其实不需要和这几个字符相比较了,只需要将模式向右滑动3个字符即可。这样的匹配过程中,实际上主串i没有回溯,只是模式串的j在变化,就降低了时间复杂度为O(l1+l2),这也就是kmp算法。

    kmp算法每趟比较过程让模式串向后滑动一个合适的位置,这个合适的位置我们可以算出来,一般称这个位置叫next表。

    先写出next表的定义,接下来再解释为什么这样定义

     

    结合这个图来解释

    先说一下,上面两个图中的S0和T0分别代表的是两个穿的长度,真正的字符串都从下标1开始。

    1)当j=1时,也就是说模式串的第一个字符就与当前位置s对应的字符不同,此时主串的下标应该+1,再和模式串第一个字符进行比较;

    2)当两个串匹配到此处时,前j-1个字符都是匹配的,到了第j个字符就不同了,此时需要把字符串t向右移动max{k}个位置。

    这个k应该满足1<k<j并且p1...pk-1=pj-k+1...pj-1.k的值可能有多个,为了不使向右移动丢失可能的匹配,选择最大的一个k,也就是max{k},其最大值为j-1;

    3)除了上面两种情况,发生匹配时,主串指针i不回溯,在最坏情况下,模式串从第1个字符开始与主串第i个字符比较,以便不丢失可能的匹配。

    上面讲解的next函数表的定义,然后下面是求next函数表的代码以及实现kmp算法。篇幅有点长,转到下一篇讲。

     

    展开全文
  • 串的模式匹配

    千次阅读 2019-10-14 19:59:39
    字串(模式串)的定位操作 在主串(也称做目标串)S中...当模式匹配成功时,函数返回模式串T的第一个字符在主串S中的位置;当模式匹配失败时,函数返回-1 朴素的模式匹配算法(Brute-Force算法) BF算法的主要思想是...
  • scala模式匹配0903.1

    2020-09-07 09:36:37
    Scala 模式匹配 案例一: 模式匹配基本写法 如果能够匹配上、会自动执行case后面的语句、默认会有自动的break 如果都匹配不上、会自动执行 case _ => 类似 java : 并且一个case里面可以写代码体 ,要添加{} ...
  • 模式匹配(Java)——烤馍片算法

    千次阅读 2020-05-05 11:06:37
    模式匹配(Java)——烤馍片算法(KMP算法) 模式匹配 模式匹配是数据结构中字符串的一种基本运算。
  • 数据结构---串的模式匹配算法介绍

    万次阅读 多人点赞 2017-02-22 10:58:37
    对于文本程序来说,找出一个子串在文本中的位置是特别重要的,我们称那个子串为模式串(pattern),然后我们称寻找的过程为:模式匹配(string match)。 2、实现算法(1)—朴素字符串匹配算法 原理:从
  • 朴素模式匹配与KMP模式匹配算法

    千次阅读 2018-07-02 10:27:07
    一、朴素模式匹配朴素模式匹配算法就是遍历主串,然后把待匹配字符串与子串进行比对,先把待匹配子串的第一个字母与主串进行匹配,若匹配成功,则两串的坐标依次 ++,匹配不成功时,主串坐标返回到开始匹配时的坐标...
  • 详细解读KMP模式匹配算法

    万次阅读 多人点赞 2016-10-06 14:18:05
    首先我们需要了解什么是模式匹配? 子串定位运算又称为模式匹配(Pattern Matching)或串匹配(String Matching)。在串匹配中,一般将主串称为目标串,将子串称为模式串。本篇博客统一用S表示目标串,T表示模式串,...
  • snort 源码分析之模式匹配引擎

    千次阅读 2020-04-12 21:39:28
    模式匹配引擎主要使用多模式匹配算法和单模式匹配算法。先由多模式匹配算法大概确定有哪些规则可能匹配成功,然后再通过单模式匹配算法去精确匹配。其配置格式如下: config detection: search-me...
  • 串的模式匹配算法,通俗地理解,是一种用来判断两个串之间是否具有"主串与子串"关系的算法。 主串与子串:如果串 A(如 "shujujiegou")中包含有串 B(如 "ju"),则称串 A 为主串,串 B 为子串。主串与子串之间的...
  • 本篇是对于KMP单模式匹配以及AC算法多模式匹配的简单讲解,KMP算法与AC算法是关键字检索中的常见算法,能够快速而高效地查找出目标字符串中的多个关键字的匹配情况,而要检索的关键字通常被称为模式串,因此模式匹配...
  • 串的应用--模式匹配算法

    千次阅读 2016-07-12 10:23:15
    子串的定位操作通常称为串的模式匹配,是串中最重要的操作之一。朴素的模式匹配算法,简单来说,就是对主串的每个字符作为子串开头,与要匹配的字符串进行匹配。对主串做大循环,每个字符开头做T的长度的小循环,...
  • KMP模式匹配算法

    千次阅读 2017-12-13 10:21:51
    朴素的模式匹配算法 对主串的每一个字符作为子串的开头,与要匹配的字符串进行匹配。对主串做大循环,每个字符开头做需匹配长度的小循环,直到匹配成功或者全部遍历完成为止 示例程序(朴素的模式匹配)int Index...
  • 字符串多模式匹配:AC算法

    万次阅读 2017-03-21 19:17:22
    早在1975年贝尔实验室的两位研究人员Alfred V. Aho 和Margaret J. Corasick就提出了以他们的名字... AC算法是一个经典的多模式匹配算法,可以保证对于给定的长度为n的文本,和模式集合P{p1,p2,…pm},在O(n)时间复杂度
  • 数据结构——串的模式匹配算法

    千次阅读 2017-05-11 18:00:05
    2、串的模式匹配算法  串的查找操作也称作串的模式匹配操作,模式匹配操作的具体含义是:在主串(也称作目标串)中,从位置start开始查找是否存在子串(也称作模式串),如在主串中查找到一个与模式串相同的子串,...
  • 字符串匹配(多模式匹配篇)

    千次阅读 2018-05-14 22:33:25
    字符串匹配(多模式匹配篇)摘要:问题的提出:众所周知,KMP算法在O(n)的时间中solve单模式串匹配问题。但怎样solve多模式串匹配问题呢?Solve:本文用简要记叙了使用trie树,trie图(AC自动机)solve该问题的...
  • JavaScript - 模式匹配

    千次阅读 2019-08-23 16:19:44
    String和RegExp对象均定义了利用正则表达式进行模式匹配和查找与替换的函数。 RegExp并不是js的基本类型。和Date一样,它只是一种具有实用API的特殊对象。正则表达式的语法很复杂,API也很丰富。RegExp是一...
  • scala-模式匹配(字符串、数组、元组、集合、类、偏函数)   Scala 提供了强大的模式匹配机制,应用也非常广泛。 一个模式匹配包含了一系列备选项,每个都开始于关键字 case。每个备选项都包含了一个模式及一到...
1 2 3 4 5 ... 20
收藏数 699,370
精华内容 279,748
关键字:

模式匹配