精华内容
下载资源
问答
  • lua之字符串模式匹配

    千次阅读 2017-09-27 17:48:15
    在string库中功能最强大的函数是: 复制代码代码如下: string.find(字符查找) ...这些函数都是基于模式匹配的。与其他脚本语言不同的是,Lua并不使用POSIX规范的正则表达式[4](也写作regexp)来进

    在string库中功能最强大的函数是:

    string.find(字符串查找)
    string.gsub(全局字符串替换)
    string.gfind(全局字符串查找)
    string.gmatch(返回查找到字符串的迭代器)


    这些函数都是基于模式匹配的。与其他脚本语言不同的是,Lua并不使用POSIX规范的正则表达式[4](也写作regexp)来进行模式匹配。主要的原因出于程序大小方面的考虑:实现一个典型的符合POSIX标准的regexp大概需要4000行代码,这比整个Lua标准库加在一起都大。权衡之下,Lua中的模式匹配的实现只用了500行代码,当然这意味着不可能实现POSIX所规范的所有更能。然而,Lua中的模式匹配功能是很强大的,并且包含了一些使用标准POSIX模式匹配不容易实现的功能。

    string.gmatch(str, pattern)     

    这是一个返回迭代器的函数. 实际的用例如下:

    s = "hello world from Lua"
    for w in string.gmatch(s, "%a+") do
     print(w)
    end


    这里是一个捕获并将配对字符分别存到不同变量的例子:

    t = {}
    s = "from=world, to=Lua"
    for k, v in string.gmatch(s, "(%w+)=(%w+)") do
     t[k]=v
    end
    for k, v in pairs(t) do
     print(k, v)
    end

    string.gsub(str, pattern, repl, n)

    原型:string.gsub (s, pattern, repl [,m])解释:这个函数会返回一个替换后的副本,原串中所有的符合参数pattern的子串都将被参数repl所指定的字符串所替换,如果指定了参数m,那么只替换查找过程的前m个匹配的子串,参数repl可以是一个字符串、表、或者是函数,并且函数可以将匹配的次数作为函数的第二个参数返回,接下来看看参数repl的含义:
    • 如果参数repl是一个常规字符串,成功匹配的子串会被repl直接替换,如果参数repl中包含转移字符%,那么可以采用%n的形式替换,当%n中的n取值1-9时,表示一次匹配中的第n个子串,当其中的n为0时,表示这次匹配的整个子串,%%表示一个单独的%
    • 如果参数repl是一个表,那么每次匹配中的第一个子串将会作为整个表的键,取table[匹配子串]来替换所匹配出来的子串,当匹配不成功时,函数会使用整个字符串来作为table的键值。
    • 如果参数repl是一个函数,那么每一次匹配的子串都将作为整个函数的参数,取function(匹配子串)来替换所匹配出来的子串,当匹配不成功时,函数会使用整个字符串来作为函数的参数。如果函数的返回值是一个数字或者是字符串,那么会直接拿来替换,如果它返回false或者nil,替换动作将不会发生,如果返回其他的值将会报错。

    以下是几个例子:

    -- 常规替换
    x = string.gsub("hello world", "(%w+)", "lua")
    print("\n",x)
    
    -- 都用匹配的第一个串*2来替换
    x = string.gsub("hello world", "(%w+)", "%1 %1")
    print("\n",x)
    
    -- 用匹配出的完成串*2来替换第一次匹配的结果
    x = string.gsub("hello world", "%w+", "%0 %0", 1)
    print("\n",x)
    
    -- 使用一个完整匹配和一个匹配的第二个串来替换
    x = string.gsub("hello world from c to lua", "(%w+) (%a+)", "%0 %2")
    print("\n",x)	--%0:hello world;%1:hello;%2:world;
    
    -- 调用系统函数来替换
    x = string.gsub("os = $OS, pathext = $PATHEXT", "%$(%w+)", os.getenv)
    print("\n",x)
    
    -- 调用自定义函数
    x = string.gsub("4 + 5 = $return 4+5$", "%$(.-)%$", function (s)
          return loadstring(s)()
        end)
    print("\n",x)
    
    -- 调用表来替换
    local t = {name="lua", version="5.1"}
    x = string.gsub("$name-$version.tar.gz", "%$(%w+)", t)
    print("\n",x)

    string.match(str, pattern, init)

    string.match()只寻找源字串str中的第一个配对. 参数init可选, 指定搜寻过程的起点, 默认为1.

    在成功配对时, 函数将返回配对表达式中的所有捕获结果; 如果没有设置捕获标记, 则返回整个配对字符串. 当没有成功的配对时, 返回nil.

    string.match("abcdaef", "a")
    -> a

    string.reverse(str)

    返回一个字符串的倒序排列

    string.reverse("abcde")
    ->edcba


    string.dump(function)

    返回指定函数的二进制代码(函数必须是一个Lua函数,并且没有上值)

    string.find(str, pattern, init, plain)

    string.find的基本应用就是用来在目标串(subject string)内搜索匹配指定的模式的串。函数如果找到匹配的串返回他的位置,否则返回nil.最简单的模式就是一个单词,仅仅匹配单词本身。比如,模式'hello'仅仅匹配目标串中的"hello"。当查找到模式的时候,函数返回两个值:匹配串开始索引和结束索引。

    s = "hello world"
    string.find(s, "hello")    --> 1    5
    string.find(s, "world")    --> 7    11
    string.find(s, "l")        --> 3    3
    string.find(s, "lll")      --> nil


    string.find函数第三个参数是可选的:标示目标串中搜索的起始位置。当我们想查找目标串中所有匹配的子串的时候,这个选项非常有用。我们可以不断的循环搜索,每一次从前一次匹配的结束位置开始。下面看一个例子,下面的代码用一个字符串中所有的新行构造一个表:

    local t = {}      -- 存放回车符的位置
    local i = 0
    while true do
        i = string.find(s, "\n", i+1)  -- 查找下一行
        if i == nil then break end
        table.insert(t, i)
    end


    string.sub(str,sPos,ePos)

    string.gsub的功能是截取字符串,他从指定起始位置截取一个字符串。string.sub可以利用string.find返回的值截取匹配的子串。
    对简单模式而言,匹配的就是其本身

    s = "hello world"
    local i, j = string.find(s, "hello")    --> 1    5
    string.sub(s, i, j)        --> hello


    string.gsub(str, sourcestr, desstr)

    string.gsub的基本作用是用来查找匹配模式的串,并将使用替换串其替换掉:

    string.gsub函数有三个参数:目标串,模式串,替换串。

    s = string.gsub("Lua is cute", "cute", "great")
    print(s)      --> Lua is great
    s = string.gsub("all lii", "l", "x")
    print(s)      --> axx xii
    s = string.gsub("Lua is great", "perl", "tcl")
    print(s)      --> Lua is great


    第四个参数是可选的,用来限制替换的范围:

    s = string.gsub("all lii", "l", "x", 1)
    print(s)          --> axl lii
    s = string.gsub("all lii", "l", "x", 2)
    print(s)          --> axx lii


    string.gsub的第二个返回值表示他进行替换操作的次数。例如,下面代码涌来计算一个字符串中空格出现的次数:

    _, count = string.gsub(str, " ", " ")


    (注意,_ 只是一个哑元变量)

    模式

    你还可以在模式串中使用字符类。字符类指可以匹配一个特定字符集合内任何字符的模式项。比如,字符类%d匹配任意数字。所以你可以使用模式串'%d%d/%d%d/%d%d%d%d'搜索dd/mm/yyyy格式的日期:

    s = "Deadline is 30/05/1999, firm"
    date = "%d%d/%d%d/%d%d%d%d"
    print(string.sub(s, string.find(s, date)))    --> 30/05/1999


    下面的表列出了Lua支持的所有字符类:

    单个字符(除^$()%.[]*+-?外): 与该字符自身配对

    .(点): 与任何字符配对
    %a: 与任何字母配对
    %c: 与任何控制符配对(例如\n)
    %d: 与任何数字配对
    %l: 与任何小写字母配对
    %p: 与任何标点(punctuation)配对
    %s: 与空白字符配对
    %u: 与任何大写字母配对
    %w: 与任何字母/数字配对
    %x: 与任何十六进制数配对
    %z: 与任何代表0的字符配对
    %x(此处x是非字母非数字字符): 与字符x配对. 主要用来处理表达式中有功能的字符(^$()%.[]*+-?)的配对问题, 例如%%与%配对
    [数个字符类]: 与任何[]中包含的字符类配对. 例如[%w_]与任何字母/数字, 或下划线符号(_)配对
    [^数个字符类]: 与任何不包含在[]中的字符类配对. 例如[^%s]与任何非空白字符配对

    当上述的字符类用大写书写时, 表示与非此字符类的任何字符配对. 例如, %S表示与任何非空白字符配对.例如,'%A'非字母的字符

    print(string.gsub("hello, up-down!", "%A", "."))
        --> hello..up.down. 4


    (数字4不是字符串结果的一部分,他是gsub返回的第二个结果,代表发生替换的次数。下面其他的关于打印gsub结果的例子中将会忽略这个数值。)在模式匹配中有一些特殊字符,他们有特殊的意义,Lua中的特殊字符如下:

    ( ) . % + - * ? [ ^ $


    '%' 用作特殊字符的转义字符,因此 '%.' 匹配点;'%%' 匹配字符 '%'。转义字符 '%'不仅可以用来转义特殊字符,还可以用于所有的非字母的字符。当对一个字符有疑问的时候,为安全起见请使用转义字符转义他。

    对Lua而言,模式串就是普通的字符串。他们和其他的字符串没有区别,也不会受到特殊对待。只有他们被用作模式串用于函数的时候,'%' 才作为转义字符。所以,如果你需要在一个模式串内放置引号的话,你必须使用在其他的字符串中放置引号的方法来处理,使用 '\' 转义引号,'\' 是Lua的转义符。你可以使用方括号将字符类或者字符括起来创建自己的字符类(译者:Lua称之为char-set,就是指传统正则表达式概念中的括号表达式)。比如,'[%w_]' 将匹配字母数字和下划线,'[01]' 匹配二进制数字,'[%[%]]' 匹配一对方括号。下面的例子统计文本中元音字母出现的次数:

    _, nvow = string.gsub(text, "[AEIOUaeiou]", "")


    在char-set中可以使用范围表示字符的集合,第一个字符和最后一个字符之间用连字符连接表示这两个字符之间范围内的字符集合。大部分的常用字符范围都已经预定义好了,所以一般你不需要自己定义字符的集合。比如,'%d' 表示 '[0-9]';'%x' 表示 '[0-9a-fA-F]'。然而,如果你想查找八进制数,你可能更喜欢使用 '[0-7]' 而不是 '[01234567]'。你可以在字符集(char-set)的开始处使用 '^' 表示其补集:'[^0-7]' 匹配任何不是八进制数字的字符;'[^\n]' 匹配任何非换行符户的字符。记住,可以使用大写的字符类表示其补集:'%S' 比 '[^%s]' 要简短些。

    Lua的字符类依赖于本地环境,所以 '[a-z]' 可能与 '%l' 表示的字符集不同。在一般情况下,后者包括 'ç' 和 'ã',而前者没有。应该尽可能的使用后者来表示字母,除非出于某些特殊考虑,因为后者更简单、方便、更高效。

    可以使用修饰符来修饰模式增强模式的表达能力,Lua中的模式修饰符有四个:

    +      匹配前一字符1次或多次
    *      匹配前一字符0次或多次
    -      匹配前一字符0次或多次
    ?      匹配前一字符0次或1次


    '+',匹配一个或多个字符,总是进行最长的匹配。比如,模式串 '%a+' 匹配一个或多个字母或者一个单词:

    print(string.gsub("one, and two; and three", "%a+", "word"))
        --> word, word word; word word


    '%d+' 匹配一个或多个数字(整数):

    i, j = string.find("the number 1298 is even", "%d+")
    print(i,j)    --> 12  15


    '*' 与 '+' 类似,但是他匹配一个字符0次或多次出现.一个典型的应用是匹配空白。比如,为了匹配一对圆括号()或者括号之间的空白,可以使用 '%(%s*%)'。( '%s*' 用来匹配0个或多个空白。由于圆括号在模式中有特殊的含义,所以我们必须使用 '%' 转义他。)再看一个例子,'[_%a][_%w]*' 匹配Lua程序中的标示符:字母或者下划线开头的字母下划线数字序列。

    '-' 与 '*' 一样,都匹配一个字符的0次或多次出现,但是他进行的是最短匹配。某些时候这两个用起来没有区别,但有些时候结果将截然不同。比如,如果你使用模式 '[_%a][_%w]-' 来查找标示符,你将只能找到第一个字母,因为 '[_%w]-' 永远匹配空。另一方面,假定你想查找C程序中的注释,很多人可能使用 '/%*.*%*/'(也就是说 "/*" 后面跟着任意多个字符,然后跟着 "*/" )。然而,由于 '.*' 进行的是最长匹配,这个模式将匹配程序中第一个 "/*" 和最后一个 "*/" 之间所有部分:

    test = "int x; /* x */ int y; /* y */"
    print(string.gsub(test, "/%*.*%*/", "<COMMENT>"))
        --> int x; <COMMENT>


    然而模式 '.-' 进行的是最短匹配,她会匹配 "/*" 开始到第一个 "*/" 之前的部分:

    test = "int x; /* x */ int y; /* y */"
    print(string.gsub(test, "/%*.-%*/", "<COMMENT>"))
        --> int x; <COMMENT> int y; <COMMENT>


    '?' 匹配一个字符0次或1次。举个例子,假定我们想在一段文本内查找一个整数,整数可能带有正负号。模式 '[+-]?%d+' 符合我们的要求,它可以匹配像 "-12"、"23" 和 "+1009" 等数字。'[+-]' 是一个匹配 '+' 或者 '-' 的字符类;接下来的 '?' 意思是匹配前面的字符类0次或者1次。

    与其他系统的模式不同的是,Lua中的修饰符不能用字符类;不能将模式分组然后使用修饰符作用这个分组。比如,没有一个模式可以匹配一个可选的单词(除非这个单词只有一个字母)。下面我将看到,通常你可以使用一些高级技术绕开这个限制。
    以 '^' 开头的模式只匹配目标串的开始部分,相似的,以 '$' 结尾的模式只匹配目标串的结尾部分。这不仅可以用来限制你要查找的模式,还可以定位(anchor)模式。比如:

    if string.find(s, "^%d") then ...


    检查字符串s是否以数字开头,而

    if string.find(s, "^[+-]?%d+$") then ...


    检查字符串s是否是一个整数。
    '%b' 用来匹配对称的字符。常写为 '%bxy' ,x和y是任意两个不同的字符;x作为匹配的开始,y作为匹配的结束。比如,'%b()' 匹配以 '(' 开始,以 ')' 结束的字符串:

    print(string.gsub("a (enclosed (in) parentheses) line", "%b()", ""))
    --> a line

    常用的这种模式有:'%b()' ,'%b[]','%b%{%}' 和 '%b<>'。你也可以使用任何字符作为分隔符。


    Lua中的正则表达式

    正则表达式由元字符按照规则(语法)组成。lua中的特殊字符是%.^$+-*?,一共12个。它们和一般字符按规则构成了lua的正则表达式。

    元字符 描述 表达式实例 完整匹配的字串
    字符
    普通字符 除去%.[]()^$*+-?的字符,匹配字符本身 Kana Kana
    . 匹配任意字符 Ka.a Kana
    % 转义字符,改变后一个字符的原有意思。当后面的接的是特殊字符时,将还原特殊字符的原意。%和一些特定的字母组合构成了lua的预定义字符集。%和数字1~9组合表示之前捕获的分组 K%wna
    %%na%%
    (a)n%1
    Kana
    %na%
    ana
    [...] 字符集(字符类)。匹配一个包含于集合内的字符。[...]中的特殊字符将还原其原意,但有下面几种特殊情况
    1. %],%-,%^作为整体表示字符']','-','^'
    2. 预定义字符集作为一个整体表示对应字符集
    3. 当]位于序列的第一个字符时只表示字符']'
    4. 形如[^...],[...-...]有特定的其他含义
    [a%]na
    [%a]na
    [%%a]na
    []]na
    [%]]na
    [a-]na
    %na
    wna
    wna
    ]na
    ]na
    -na
    [...-...] -表示ascii码在它前一个字符到它后一个字符之间的所有字符 [a-z]a na
    [^...] 不在...中的字符集合。 [^0-9]na
    [^^0-9]na
    Kna
    Kna
    重复(数量词)
    * 表示前一个字符出现0次或多次 [0-9]*
    [a-z]*9*
    2009
    na
    + 表示前一个字符出现1次或1次以上 n+[0-9]+ n2009
    ? 表示前一个字符出现0次或1次 n?[0-9]+ 2009
    预定义字符集
    %s 空白符[ \r\n\t\v\f] an[%s]?9 an 9
    %p 标点符号 an[%p]9 an.9
    %c 控制字符    
    %w 字母数字[a-zA-Z0-9] [%w]+ Kana9
    %a 字母[a-zA-Z] [%a]* Kana
    %l 小写字母[a-z] -
    %u 大写字母[A-Z] -
    %d 数字[0-9] -
    %x 16进制数[0-9a-fA-F] -
    %z ascii码是0的字符 -
    分组
    (...) 表达式中用小括号包围的子字符串为一个分组,分组从左到右(以左括号的位置),组序号从1开始递增。 ab(%d+)
    (%d+)%1
    ab233
    123123
    边界匹配(属于零宽断言)
    ^ 匹配字符串开头 ^(%a)%w* abc123
    $ 匹配字符串结尾 %w*(%d)$ abc123
    %b
    %bxy 平衡匹配(匹配xy对)。这里的x,y可以是任何字符,即使是特殊字符也是原来的含义,匹配到的子串以x开始,以y结束,并且如果从x开始,每遇到x,计算+1,遇到y计数-1,则结束的y是第一个y使得计数等于0。就是匹配成对的符号,常见的如%b()匹配成对的括号


    展开全文
  • sql字符串模式匹配

    万次阅读 2009-11-20 16:02:00
    MySQL提供标准的SQL模式匹配,以及一种基于象Unix实用程序如vi、grep和sed的扩展正则表达式模式匹配的格式。 标准的SQL模式匹配SQL的模式匹配允许你使用“_”匹配任何单个字符,而“%”匹配任意数目字符(包括零个...

     MySQL提供标准的SQL模式匹配,以及一种基于象Unix实用程序如vigrepsed的扩展正则表达式模式匹配的格式。 标准的SQL模式匹配

    SQL的模式匹配允许你使用“_”匹配任何单个字符,而“%”匹配任意数目字符(包括零个字符)。在 MySQL中,SQL的模式缺省是忽略大小写的。下面显示一些例子。注意在你使用SQL模式时,你不能使用=!=;而使用LIKENOT LIKE比较操作符。

    例如,在表pet中,为了找出以“b”开头的名字:

    mysql> SELECT * FROM pet WHERE name LIKE "b%";

    +--------+--------+---------+------+------------+------------+
    | name   | owner  | species | sex  | birth      | death      |
    +--------+--------+---------+------+------------+------------+
    | Buffy  | Harold | dog     | f    | 1989-05-13 | NULL       |
    | Bowser | Diane  | dog     | m    | 1989-08-31 | 1995-07-29 |
    +--------+--------+---------+------+------------+------------+

     

    为了找出以“fy”结尾的名字:

    mysql> SELECT * FROM pet WHERE name LIKE "%fy";

    +--------+--------+---------+------+------------+-------+
    | name   | owner  | species | sex  | birth      | death |
    +--------+--------+---------+------+------------+-------+
    | Fluffy | Harold | cat     | f    | 1993-02-04 | NULL  |
    | Buffy  | Harold | dog     | f    | 1989-05-13 | NULL  |
    +--------+--------+---------+------+------------+-------+

     

    为了找出包含一个“w”的名字:

    mysql> SELECT * FROM pet WHERE name LIKE "%w%";

    +----------+-------+---------+------+------------+------------+
    | name     | owner | species | sex  | birth      | death      |
    +----------+-------+---------+------+------------+------------+
    | Claws    | Gwen  | cat     | m    | 1994-03-17 | NULL       |
    | Bowser   | Diane | dog     | m    | 1989-08-31 | 1995-07-29 |
    | Whistler | Gwen  | bird    | NULL | 1997-12-09 | NULL       |
    +----------+-------+---------+------+------------+------------+

     

    为了找出包含正好5个字符的名字,使用“_”模式字符:

    mysql> SELECT * FROM pet WHERE name LIKE "_____";

    +-------+--------+---------+------+------------+-------+
    | name  | owner  | species | sex  | birth      | death |
    +-------+--------+---------+------+------------+-------+
    | Claws | Gwen   | cat     | m    | 1994-03-17 | NULL  |
    | Buffy | Harold | dog     | f    | 1989-05-13 | NULL  |
     
    扩展正则表达式模式匹配

    MySQL提供的模式匹配的其他类型是使用扩展正则表达式。当你对这类模式进行匹配测试时,使用REGEXPNOT REGEXP操作符(RLIKENOT RLIKE,它们是同义词)

    扩展正则表达式的一些字符是:

    .”匹配任何单个的字符。

    一个字符类“[...]”匹配在方括号内的任何字符。例如,“[abc]”匹配“a”、“b”或“c”。为了命名字符的一个范围,使用一个“-”。“[a-z]”匹配任何小写字母,而“[0-9]”匹配任何数字。

    * ”匹配零个或多个在它前面的东西。例如,“x*”匹配任何数量的“x”字符,“[0-9]*”匹配的任何数量的数字,而“.*”匹配任何数量的任何东西。

    正则表达式是区分大小写的,但是如果你希望,你能使用一个字符类匹配两种写法。例如,“[aA]”匹配小写或大写的“a”而“[a-zA-Z]”匹配两种写法的任何字母。

    如果它出现在被测试值的任何地方,模式就匹配(只要他们匹配整个值,SQL模式匹配)

    为了定位一个模式以便它必须匹配被测试值的开始或结尾,在模式开始处使用“^”或在模式的结尾用“$”。

    为了说明扩展正则表达式如何工作,上面所示的LIKE查询在下面使用REGEXP重写:

    为了找出以“b”开头的名字,使用“^”匹配名字的开始并且“[bB]”匹配小写或大写的“b”:

     

    mysql> SELECT * FROM pet WHERE name REGEXP "^[bB]";

    +--------+--------+---------+------+------------+------------+
    | name   | owner  | species | sex  | birth      | death      |
    +--------+--------+---------+------+------------+------------+
    | Buffy  | Harold | dog     | f    | 1989-05-13 | NULL       |
    | Bowser | Diane  | dog     | m    | 1989-08-31 | 1995-07-29 |
    +--------+--------+---------+------+------------+------------+

     

    为了找出以“fy”结尾的名字,使用“$”匹配名字的结尾:

     

    mysql> SELECT * FROM pet WHERE name REGEXP "fy$";

    +--------+--------+---------+------+------------+-------+
    | name   | owner  | species | sex  | birth      | death |
    +--------+--------+---------+------+------------+-------+
    | Fluffy | Harold | cat     | f    | 1993-02-04 | NULL  |
    | Buffy  | Harold | dog     | f    | 1989-05-13 | NULL  |
    +--------+--------+---------+------+------------+-------+

     

    为了找出包含一个“w”的名字,使用“[wW]”匹配小写或大写的“w”:

     

    mysql> SELECT * FROM pet WHERE name REGEXP "[wW]";

    +----------+-------+---------+------+------------+------------+
    | name     | owner | species | sex  | birth      | death      |
    +----------+-------+---------+------+------------+------------+
    | Claws    | Gwen  | cat     | m    | 1994-03-17 | NULL       |
    | Bowser   | Diane | dog     | m    | 1989-08-31 | 1995-07-29 |
    | Whistler | Gwen  | bird    | NULL | 1997-12-09 | NULL       |
    +----------+-------+---------+------+------------+------------+

     

    既然如果一个正规表达式出现在值的任何地方,其模式匹配了,就不必再先前的查询中在模式的两方面放置一个通配符以使得它匹配整个值,就像如果你使用了一个SQL模式那样。

    为了找出包含正好5个字符的名字,使用“^”和“$”匹配名字的开始和结尾,和5个“.”实例在两者之间:

    mysql> SELECT * FROM pet WHERE name REGEXP "^.....$";

    +-------+--------+---------+------+------------+-------+
    | name  | owner  | species | sex  | birth      | death |
    +-------+--------+---------+------+------------+-------+
    | Claws | Gwen   | cat     | m    | 1994-03-17 | NULL  |
    | Buffy | Harold | dog     | f    | 1989-05-13 | NULL  |
    +-------+--------+---------+------+------------+-------+

     

    你也可以使用“{n}”“重复n次”操作符重写先前的查询:

     

    mysql> SELECT * FROM pet WHERE name REGEXP "^.{5}$";

    +-------+--------+---------+------+------------+-------+
    | name  | owner  | species | sex  | birth      | death |
    +-------+--------+---------+------+------------+-------+
    | Claws | Gwen   | cat     | m    | 1994-03-17 | NULL  |
    | Buffy | Harold | dog     | f    | 1989-05-13 | NULL  |
    +-------+--------+---------+------+------------+-------+

    4.3节介绍了有关字符串模式匹配的有关知识。标准的SQL模式匹配是SQL语言的标准,可以被其它关系数据库系统接受。扩展正规表达式模式匹配是根据Unix系统的标准开发了,一般只可使用在MySQL上,但是其功能要比标准的SQL模式匹配更强。

     

    展开全文
  • 字符匹配(多模式匹配篇)

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

    字符串匹配(多模式匹配篇)

    摘要:

    问题的提出:众所周知,KMP算法在O(n)的时间中solve单模式串匹配问题。但怎样solve多模式串匹配问题呢?

    Solve:本文用简要记叙了使用trie树,trie图(AC自动机)solve该问题的方法。

    关键字:

    字符串,多模式串匹配,trie树,trie图,AC自动机。

    前言:

    KMP算法是一种极其优秀的单模式串匹配算法,它通过前缀函数fail来减少匹配次数,以达到O(n)的单串匹配。但当KMP算法用于解决多模式串匹配问题时,时间复杂度为O(nq),十分低效。

    因此,我们去探索一些更适合于多模式串匹配问题的算法用以解决这个问题。

    第1节主要介绍trie树。

    第2节主要介绍trie图。

    第三节给出一些例题。

    1.trie树

    1.0问题的引入:

           给定一个原串s,n个模式串st[i],求st[i]是否出现在s中。

    1.1字典树的定义:


    又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。

    ——来源于百度百科

    1.2字典树的性质:

         根节点不包含字符,除根节点外每一个节点都只包含一个字符; 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串; 每个节点的所有子节点包含的字符都不相同。

         每一个节点u都包含next[v],value。

         next[v]表示节点u的v边指向的节点编号。

         value表示危险节点所属的模式串编号,若value=0表示这不是一个危险节点。

         根节点表示空串。

         这样一棵trie树的深度为O(max(len)+1)

         可以发现当且仅当s1是s2的前缀,那么在trie树上,s2的路径是包含s1的路径的。

             

    1.2字典树的实现:

    字典树的操作是十分简单的(建议读者根据性质自己推导实现过程)。

    插入:

    void build_trie_tree(char *st,int len,int p)
    {
    	int x=1;
    	for (int i=0;i<len;i++)
    	{
    		if (trie[x].next[st[i]]==0)       //若该边不存在,新建点和边。
    		{
    			nodenum++;
    			trie[x].next[st[i]]=nodenum;
    		}
    		x=trie[x].next[st[i]];            //跳转至下一个节点。
    	}
    	trie[x].value=p;                               //标记是否为危险节点。
    }

    (删除一个子树的操作不再叙述,基本思想是增加一个tag懒标记,表示此节点及其子树被删除。)

    查询(查询某一字符串是否在trie树中):

    bool query_trie_tree(char *st,int len)
    {
    	int x=1;
    	for (int i=0;i<len;i++) x=trie[x].next[st[i]];   //跳转至目标节点
    	if (!trie[x].value) return 1;
    }

    查询2(多串查询):

    我们只需要枚举起始位置i,寻找st[i->j](i<=j<=len)是否出现即可。

    void query_trie_tree(char *st,int k,int len)
    {
    	int x=1;
    	for (int i=k;i<len;i++)
    	{
    	    x=trie[x].next[st[i]];                    //跳转 
    	    if (x) return;                            //匹配失败退出 
    	    if (trie[x].value) fst[trie[x].value]=k;  //fst[i]记录i模式串出现在原串中的起始位置 
    	}
    }
    void work(char *st,int len)
    {
    	for (int i=0;i<len;i++)
    	    query_trie_tree(st,i,len);             //枚举所有起点位置 
    }


    1.4trie树的分析:(注:下文中|SIGMA|表示字符集大小,而sigma表示求和函数)

    构造出trie树的结构,构造时间是O(sigma(len)),单串匹配的时间复杂度很明显是O(len)级别的。

    多串匹配需要枚举原串的起始点u,再从trie树中查询,时间为O(lens*max(len))

    比起这个,更让我们关心的是空间复杂度,O(|SIGMA|n)。倘若空间不足,可以将next[v]用边表的形式记录下来,或者用左儿子,右兄弟的方法记录。

    这样的数据结构无论从时间或是空间上都和KMP相差无几,但更加形象具体了。那么如何改变这个数据结构使它能够完成多串匹配任务呢?


    注:将trie树从上到下,从左到右标号,根为1


    我们发现在trie树上多串匹配,会产生许多浪费。

    比如模式串为ab。

    以上图中的trie树来匹配,跳转顺序是

    1->2->5(ab)

    1->3(b)

    而匹配ab时已经将b匹配了一遍,但在做完ab之后却返回了根,重新匹配了b,得不偿失。

    所以想要优化trie树,就要使每一次精确跳转到最有效的位置。

    进入到trie图时代。


    2.trie图

    2.0trie图的引入——解决上述问题:

    什么是精确跳转呢?


    在这个图中,abc的精确跳转应该是bc。

    abd的精确跳转为根(空串)

    字符串s的精确跳转节点是trie树中存在的s最长的后缀,称为后缀fail。

    2.1trie图的概念:

    在trie树上添加前缀指针fail并补齐trie树的边,所构造的图。

    2.2trie图的性质:

    trie图的目的是让每一次都精确地跳转。

            

            如该图中的的fail应该指向bc。

           节点u的fail应该为u的父亲节点的fail点的该边。(fail[u]=trie[father[fail[u]]].next[ch])

           读者可以计算一下当trie图中只有单串的时候,fail和KMP的next两个数组有什么特殊的联系。

           能够很轻易地看出:若trie图按0开始编号,next[i]=fail[i]

    2.3trie图的实现:(建议读者自行思考后对照)

       构造trie图:

    void build_trie_graph()
    { 
    	trie[1].fail=1;                            //根的后缀为根
    	for (int i=1;i<=p;i++)
    	if (trie[1].next[i]) 
    	{
    		trie[trie[1].next[i]].fail=1;
    		que.push(trie[1].next[i]);
    	}                                          //根的儿子的后缀为根
    	else trie[1].next[i]=1;                    //根的新边为根
    	
    	while (!que.empty())
    	{
    		int q=que.front();
    		que.pop();
    		for (int i=1;i<=p;i++)
    		{
    			int v=trie[q].next[i];
    			if (v)
    			{
    				trie[v].fail=trie[trie[q].fail].next[i];
    				que.push(v);
    			}
    			else trie[q].next[i]=trie[trie[q].fail].next[i];
    		}
    		if (trie[trie[q].fail].value) trie[q].value=trie[trie[q].fail].value;
    	}
    }

    遍历:

    void query_trie_tree(char *st,int len)
    {
    	int x=1;
    	for (int i=0;i<len;i++) 
    	{ 
    	    if (!trie[x].value) solve_probleam();
    		x=trie[x].next[st[i]];   //跳转至目标节点
    	}
    }


    3.来几道例题练练手!

    3.1  Video Game

    Bessie is playing a video game! In the game, the three letters 'A', 'B',

    and 'C' are the only valid buttons. Bessie may press the buttons in any
    order she likes; however, there are only N distinct combos possible (1 <= N
    <= 20). Combo i is represented as a string S_i which has a length between 1
    and 15 and contains only the letters 'A', 'B', and 'C'.

    Whenever Bessie presses a combination of letters that matches with a combo,
    she gets one point for the combo. Combos may overlap with each other or
    even finish at the same time! For example if N = 3 and the three possible
    combos are "ABA", "CB", and "ABACB", and Bessie presses "ABACB", she will
    end with 3 points. Bessie may score points for a single combo more than once.

    Bessie of course wants to earn points as quickly as possible. If she
    presses exactly K buttons (1 <= K <= 1,000), what is the maximum number of
    points she can earn?

    给你个模式串(每个长度≤15,1≤N≤20),串中只含有“ABC”三种字母。求一长度为K(1≤K≤1000)的字符串,使得匹配数最大(重复匹配计多次),输出最大值。

    题解:先构造trie图,然后动态规划。

    f[step][u]表示第step步走到u点经过的最多危险节点数量。

    f[step+1][trie[u].next[k]]=max{f[step+1][trie[u].next[k]],f[step[u]+trie[trie[u].next[k]].value }

    #include<bits/stdc++.h>
    using namespace std;
    const int MAXANS=10000000;
    struct node
    {
        int ch[5],fail,value;
    } trie[505];
    int nodenum=1,n,m;
    int f[1005][505];
    char st[25];
    queue<int> que;
    int smax(int x,int y){return x>y?x:y;}
    void build_trie_tree(char *st,int len)
    {
        int u=1;
        for (int i=0;i<len;i++)
        {
            if (!trie[u].ch[st[i]-64])
            {
                nodenum++;
                trie[u].ch[st[i]-64]=nodenum;
            }
            u=trie[u].ch[st[i]-64];
        }
        trie[u].value++;
    }
    void build_trie_graph()
    {
        trie[1].fail=1;
        for (int i=1;i<=3;i++)
            if (trie[1].ch[i])
            {
                trie[trie[1].ch[i]].fail=1;
                que.push(trie[1].ch[i]);
            }
            else trie[1].ch[i]=1;
        while (!que.empty())
        {
            int u=que.front();
            que.pop();
            for (int i=1;i<=3;i++)
            if (trie[u].ch[i])
            {
                trie[trie[u].ch[i]].fail=trie[trie[u].fail].ch[i];
                que.push(trie[u].ch[i]);
            }
            else trie[u].ch[i]=trie[trie[u].fail].ch[i];
            if (trie[trie[u].fail].value) 
                trie[u].value+=trie[trie[u].fail].value;
        }
    }
    void solve()
    {
        for (int step=0;step<=m;step++)
            for (int i=1;i<=nodenum;i++)
            f[step][i]=-MAXANS;
        f[0][1]=0;
        for (int step=0;step<m;step++)
            for (int i=1;i<=nodenum;i++)
                for (int j=1;j<=3;j++)
                {
                    int v=trie[i].ch[j];
                    f[step+1][v]=smax(f[step+1][v],f[step][i]+trie[v].value);
                }
        int ans=0;
        for (int i=2;i<=nodenum;i++) ans=smax(ans,f[m][i]); 
        printf("%d\n",ans); 
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
        {
            scanf("%s",st);
            build_trie_tree(st,strlen(st));
        }
        build_trie_graph();
        solve();
        return 0;
    }
    

    OJ上实测速度很快。只用了20MS(rank1膨胀逃)。


    3.2阿狸的打字机

    BZOJ2434 阿狸的打字机
    阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和’B’、’P’两个字母。 
    经阿狸研究发现,这个打字机是这样工作的: 
    ·输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。 
    ·按一下印有’B’的按键,打字机凹槽中最后一个字母会消失。 
    ·按一下印有’P’的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。 
    例如,阿狸输入aPaPBbP,纸上被打印的字符如下: 

    aa 
    ab 
    我们把纸上打印出来的字符串从1开始顺序编号,一直到n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数(x,y)(其中1≤x,y≤n),打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。 
    阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?
    Input
    输入的第一行包含一个字符串,按阿狸的输入顺序给出所有阿狸输入的字符。
    第二行包含一个整数m,表示询问个数。
    接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y,表示第i个询问为(x, y)。
    Output
    输出m行,其中第i行包含一个整数,表示第i个询问的答案。
    Sample Input
    aPaPBbP
    3
    1 2
    1 3
    2 3
    Sample Output 
    2
    1
    0
    Hint
    1<=N<=10^5
    1<=M<=10^5
    输入总长<=10^5

    明显的trie图。

    不解释,大佬们都会的。

    noi压轴题原来这么简单!!!(逃))



    3.3宇宙队神题!

    题目受宇宙队管制,暂时无法查看。


    3.4经典好题!

    POJ 1204 Word Puzzles

    POJ 1625 Censored! 

    POJ 2778 DNA Sequence 

    HDU 2457 DNA repair

    ural 1269. Obscene Words Filter

    [BZOJ1195][HNOI2006]最短母串


    4.总结

    trie树,trie图还是属于简单易写的匹配算法。

    trie树,trie图一般用于解决三种问题:

    1.多个字符串的存储。

    2.多个字符串的匹配、查询、字符串树(图)上操作。

    3.辅助其他算法(如DP等)存取数据。

    大家有时间可以对比一下KMP和trie图的其他性质的相同点。

    trie


    展开全文
  • string(字符) 字符由一对双引号或单引号来表示 string1="this is a string1" string2="this is string2" print(string1) print(string2) 也可以用2个方括号"[[]]"来表示“一块”字符。 html=[[ 百度...

    string(字符串)

    字符串由一对双引号或单引号来表示

    string1="this is a string1"
    string2="this is string2"
    print(string1)
    print(string2)


    也可以用2个方括号"[[]]"来表示“一块”字符串。

    html=[[
    <html>
    <head></head>
    <body>
    	<a href="www.baidu.com">百度一下</a>
    </body>
    </html>
    ]]
    print(html)


    在一个数字字符串上进行算术操作时,Lua会尝试将这个数字字符串转成一个数字:

    print("2"+6)
    print("2" + "6")
    print("2+6")
    print("-2e2" * "6")
    print("hello"+1)


    字符串连接使用的是.. ,如:

    print("a" .. "b")
    print("123" .. "456")


    使用#来计算字符串的长度,放在字符串前面,如下

    len="www.baidu.com"
    print(#len)
    print(#"www.baidu.com")


    字符串操作

    string.upper(argument) 字符串全部转为大写字母

    string.lower(argument) 字符串全部转为小写字母

    string.sub(s,i,j)

    将从s提取一段字符串,从i到j(闭区间[i,j]),也可以使用负索引值,将从字符串尾部算起,-1是最后一个字符,-2是倒数第二,这么做的好处是当我们要提取直到末尾几个字符时,从后面数其非常方便。

    s="[hello,world]"
    print(string.sub(s,2,-2))



    string.gsub(mainString, findString, replaceString, num)

    字符串替换操作,mainString为要替换的字符串,findString为被替换的字符,replaceString要替换的字符,num替换次数(可以忽略则全部替换)

    print(string.gsub("aaaa","a","z",3))


    string.find(str, substr,[init,[end]])

    在一个指定的目标字符串中搜索指定的内容(第三个参数为索引),返回其具体位置。不存在则返回nil

    print(string.find("Hello lua user","lua",1))
    print(string.find("Hello lua user","lua"))


    string.reverse(arg) 字符串反转

    print(string.reverse("lua"))


    string.format(...) 返回一个类似print的格式化字符串

    print(string.format("the value is:%d",4))
    

    string1="Lua"
    string2="Tutorial"
    -- 基本字符串格式化
    print(string.format("basic format %s %s",string1,string2))
    -- 日期格式化
    date=9; month=8; year=2016
    print(string.format("date format %02d/%02d/%03d",date,month,year))
    -- 02d表示2表示宽度,如果整数不够2列就补0,如果大于2,无影响
    -- 十进制格式化
    print(string.format("%.4f",1/3))


    string.char(arg)和string.byte(arg[,int])

    char将整型数字转成字符并连接,byte转换字符为整数值(可以指定某个字符,默认第一个字符)。

    print(string.char(97,98,99,100))
    print(string.byte("ABCD",4))
    print(string.byte("ABCD"))



    -- 字符转换
    -- 转换第一个字符
    print(string.byte("Lua"))
    -- 转换第三个字符
    print(string.byte("Lua",3))
    -- 转换末尾第一个字符
    print(string.byte("Lua",-1))
    -- 第二个字符
    print(string.byte("Lua",2))
    -- 转换末尾第二个字符
    print(string.byte("Lua",-2))
    
    -- 整数ASCII码转换为字符
    print(string.char(97))



    string.len(arg) 计算字符串长度

    print(string.len("abc"))


    string.rep(string,n) 返回字符串string的n个拷贝

    print(string.rep("abcd",2))


    .. 连接两个字符串

    print("www.bidu"..".com")


    模式匹配

    Lua string库里最强大的函数是那些模式匹配函数:find,match,gsub,gmatch。和其他脚本语言不通,Lua既没有用POSIX的正则表达式,也没有用perl的正则表达式。原因是实现这些导致lua占用更多内存,而Lua的初衷是小巧的,嵌入应用的语言。Lua用少于500行的代码实现了自己的一套模式匹配,虽然不如标准的正则表达式强(一般需要4000以上代码),但也足够强大。

    string.find将查找目标模板在给定字符串中出现的位置,找到返回起始和结束位置,没找到返回nil。

    s="hello,world"
    i,j = string.find(s,"hello")
    print(string.sub(s,i,j))
    


    string.find还可以给定起始搜索位置,当你想找出所有出现的位置时,这个参数就很有用,例如想知道换行符出现在那些地方:

    s="hello\nworld\nnihao\n"
    local t={}
    local i=0
    while true do
    	i=string.find(s,"\n",i+1)
    	if i==nil then
    		break
    	end
    	t[#t+1]=i
    end
    
    for i,v in ipairs(t) do
    	print(i.."--"..v)
    end


    string.match和string.find类似,都市在指定的string中查找相应的模式。不同的是,它返回的是找到的那部分string

    print(string.match("hello,world","hello"))


    对于可变模式

    date="now is 2016/8/9 10:51"
    date_m=string.match(date,"%d+/%d+/%d+")
    print(date_m)


    string.gsub有三个参数,给定字符串,匹配模式和替代字符串。作用就是将所有符合匹配模式的地方都替换成替代字符串。并返回替换后的字符串,以及替换次数。

    s,n=string.gsub("Lua is cute","cute","great")
    print(s,n)


    string.gmatch函数将返回一个迭代器,用于迭代所有出现在给定字符串中的匹配字符。


    Lua支持的所有字符类:

           . 任意字符

          %a 字母

          %c 控制字符

          %d 数字

          %l 小写字母

          %p 标点字符

          % s 空白符

          %u 大写字符

          %w 字母和数字

         %x 十六进制数字

         %z 代表0的字符

    上面字符类的大写形式表示小写所代表的集合的补集。例如“%A”表示非字母的字符

    print(string.gsub("hello,world!","%A","."))


    Lua模式匹配中的特殊字符

    () % + - * ? [ ^ $

    '^'开头表示只匹配目标串的开始部分

    如果作用在集合中,补集 [^0-9]表示非数字

    '$'结尾表示只匹配目标串的结尾部分

    可以使用修饰符来修饰模式增强模式的表达能力,Lua中的模式修饰符有4个:

    + >=1

    * >=0

    - >=1

    ? 0次或1词

    ‘+’匹配一个或多个字符,总是进行最长的匹配。

    ‘-’匹配一个或多个字符,总是进行最短匹配。

    捕获

    捕获机制允许一个模式串中的一部分来匹配目标串中的一部分。写法是模式串中你需要捕获的那部分用()括起来。

    pair="name = yhk"
    key, value=string.match(pair,"(%a+)%s*=%s*(%a+)")
    print(key,value)


    分隔字符串

    s="aA_B_C"
    t=string.gmatch(s,"%a+")
    print(t)
    print(type(t))
    a={}
    for w in t do
    	table.insert(a,w)
    end
    
    for k,v in pairs(a) do
    	print(k,v)
    end


    s="12	aA B C"
    a={}
    id,sent=string.match(s,"(%d+)\t+(.+)")
    print(id)
    print(type(id))
    print(sent)
    print(type(sent))













    展开全文
  • 13.字符-模式匹配

    千次阅读 2015-01-10 20:38:14
    一般提起字符的相关算法,就是几个基本的...但是实际应用中,模式匹配index是应用非常广泛的字符操作,我们倾向于不依赖其他的操作来实现它。   一般匹配 如下图,在目标字符S中查找模式字符T的最直白的...
  • 模式匹配函数 在string库中功能最强大的函数是: 复制代码代码如下: string.find(字符查找) string.gsub(全局字符替换) string.gfind(全局字符查找) string.gmatch
  • MySQL中的字符串模式匹配

    万次阅读 2012-11-04 16:54:18
    MySQL提供标准的SQL模式匹配,以及一种基于象Unix实用程序如vi、grep和sed的扩展正则表达式模式匹配的格式。 标准的SQL模式匹配 SQL的模式匹配允许你使用“_”匹配任何单个字符,而“%”匹配任意数目字符(包括零...
  • 用IPTables实现字符串模式匹配

    千次阅读 2007-01-03 18:06:00
    用IPTables实现字符串模式匹配用IPTables实现字符串模式匹配 用iptables -m string 过滤字符串的安全策略应用作者:流云出处:LinuxAid论坛日期:2002-03-18自1995年ipfwadm开始进入1.2.1的核心,Linux的防火墙实现...
  • 模式匹配算法

    千次阅读 2019-06-16 16:32:07
    最近在学数据结构中的,现在来写一写我对的不同模式匹配算法的理解: 声明:首先需要注意这里面的的存储结构,它并不是普通的像C语言中的字符一样在每个末尾有一个结尾标志‘/0’,然而这里是通过在数组...
  • 字符模式匹配:BM算法

    千次阅读 2017-03-19 15:38:03
    完成字符匹配的算法,其在绝大多数场合的性能表现,比KMP算法还要出色,下面我们就来详细了解一下这一出色的单模式匹配算法,在此之前推荐读者读一下我的另一篇文章《字符模式匹配:KMP算法》,对于透彻理解BM...
  • 模式匹配算法(KMP算法,BF算法+算法详解+实现代码) 子串的定位操作是找子串在主中从第pos个字符后首次出现的位置,又被称为模式匹配 一、BF模式匹配算法 BF算法思想:Brute-Force算法又称蛮力匹配算法...
  • ------ 本文是学习算法的笔记,《数据...实际上,这些功能最基本的原理就是字符串匹配算法,也就是通过维护一个敏感词的字典,当用户输入一段文字内容之后,通过字符串匹配算法,来查找用户输入的这段文字,是否包含...
  • 模式匹配:一个主和多个模式中间的匹配问题。 当然,聪明的你一定会问难道之前所学的单模式匹配的算法就不能用;爱解决问题吗? 答案是当然可以,但是用单模式的字符算法解决这类问题总体的时间开销就会大很...
  • 1、模式匹配算法 前端时间在复习KMP算法时在网上看到了一篇关于KMP的博文,讲的非常详细,在这里给大家分享下:点击打开链接 在模式匹配算法中主要有两种算法,BF算法与KMP算法,在这里我不准备详细介绍这...
  • 字符串匹配算法(单模式串

    千次阅读 2019-02-17 22:37:22
    本文是数据结构与算法之美的学习笔记 ...字符匹配算法有:单模式串匹配算法(BF算法,RK算法,BM算法,KMP算法), 多模式串匹配算法(Trie树,AC自动机) BF(Brute Force)算法 基础概念:如果我...
  • 手机号码规则模式匹配所有匹配

    千次阅读 2012-12-14 10:43:43
    内网用户能够设置规则(AAAA、ABCD、_ABC……),外网用户可以通过这些规则进行模式匹配。这里, 我需要解释一下所谓的规则:ABCD的代表递增的4个数字、AAAA代表4个同样的数字、_代表占位符表示0~9的数字 比如:比如...
  • 模式匹配的应用很常见,比如在文字处理软件中经常用到的查找功能。我们用如下函数来表示对字串位置的定位: int index(const string &Tag,const string &Ptn,int pos)  其中,Tag为主,Ptn为子(模式)...
  • 字符串匹配算法(多模式串

    千次阅读 2019-02-23 22:35:40
    上一篇了解了单模式串匹配算法,现在来学习多模式串匹配算法,首先需要了解Trie树 Trie树的概念 Trie树也叫字典树或者前缀树,它是一个树形的结构。是一种专门用来处理字符串匹配的数据结构,用来解决在一组字符中...
  • 符号“$”表示匹配字符的结尾,即字符的结尾满足匹配模式的要求。 在 MULTILINE 模式(搜索标记中包含re.MULTILINE,关于搜索标记的含义请见《第11.2节 Python re模块函数概览》)下,本匹配模式是按行來搜索的...
  • /* ...*All rights reserved. *文件名称:main.cpp *作者:张旺华 *完成日期: 2016 年 7 月 ...*问题描述:编写一个程序实现模式的各种模式匹配 * */ #include #define MaxSize 100 //最多的字符个数 typedef struc
  • !顺序的各种模式匹配运算

    千次阅读 2013-01-27 15:20:58
    /*exp4-3.cpp*/ #include #include #define MaxSize 100 typedef struct .../*定义可容纳MaxSize个字符的空间*/ .../*标记当前实际长*/ }SqString; extern void StrAssign(SqString &str,char cstr[]
  • KMP算法其实并不是效率最高的字符串匹配算法,实际应用的并不多,各种文本编辑器的“查找”功能大多采用的是BM算法(Boyer Moore)。BM算法效率更高,更容易理解。 2. BM算法分析: (1) 假定字符为"HERE IS ...
  • 编写一个程序,实现顺序的各种模式匹配运算,并在此基础上完成如下功能: (1)建立“abcabcdabcdeabcdefabcdefg”目标s和“abcdeabcdefab”模式t。 (2)采用简单匹配算法求t在s中的位置。 (3)由模式...
  • java模式匹配 如果您使用的是Java,那么您很有可能以前已经看过它的模式匹配。 String#matches(String)方法在内部使用Pattern类型,该类型包含更复杂的功能: 通过编译正则表达式来创建Pattern 。 该模式与任何...
  • Scala-模式匹配

    千次阅读 2020-08-30 22:58:14
    三、 模式匹配类型 3.1 匹配常量 3.2 匹配类型 3.3 匹配数组 3.4 匹配列表 3.5 匹配元组 3.6 匹配对象及样例类 四、 变量声明中的模式匹配 五、 for表达式中的模式匹配 六、 偏函数中的模式匹配(了解) ...
  • 的普通模式匹配算法,大体思路是:模式从主的第一个字符开始匹配,每匹配失败,主中记录匹配进度的指针 i 都要进行 i-j+1 的回退操作(这个过程称为“指针回溯”),同时模式向后移动一个字符的位置。...
  • 符号“^”为插入符,也称为脱字符,在Python中脱字符表示匹配字符的开头,即字符的开头满足匹配模式的要求。这个功能有点类似搜索函数match,只是这是通过搜索模式来指定,而match是通过函数来指定。 在 ...
  • Scala模式匹配

    千次阅读 2019-12-28 22:45:24
    Scala的模式匹配,比java的功能更加全面,应用比较广泛 Scala中提供本类(case class),对模式匹配进行优化 package day1228 object Demo extends App { /** * 模式匹配 * */ //定义一个变量 val ch1 = "*...
  • Lua 模式匹配

    千次阅读 2016-12-06 21:39:53
    前两次用到的关于字符中去掉 用到的模糊匹配是 Result = string.gsub(str,"",","); 指任意到">"的字符  . 匹配除换行符以外的任意字符  /w 匹配字母或数字或下划线或汉字  /s 匹配任意的空白符  /d...
  • 1.掌握模式匹配操作。 实验要求: 1、 分别使用BF和KMP算法完成模式匹配。 实验过程: 1、 设计完成next值的计算函数; 2、 设计完成修正next值的函数; 3、 KMP算法代码; 4、 输

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 254,319
精华内容 101,727
关键字:

串的模式匹配功能