精华内容
下载资源
问答
  • 字符串匹配问题

    千次阅读 2007-11-01 13:27:00
    1 术语定义在字符串匹配问题中,我们期待察看串T中是否含有串P。其中串T被称为目标串,串S被称为模式串。2 朴素匹配算法进行字符串匹配,最简单的一个想法是: public class SimpleMatch { public int StringMatch...
      
    

    1 术语定义

    在字符串匹配问题中,我们期待察看串T中是否含有串P。
    其中串T被称为目标串,串S被称为模式串。

    2 朴素匹配算法

    进行字符串匹配,最简单的一个想法是:

    public   class  SimpleMatch  {
      
    public   int  StringMatch(String target,String patten)  {
          
    int  tl  =  target.length();
          
    int  pl  =  patten.length();
          
    int  i  =   0 ;
          
    int  j  =   0 ;
          
    while (i  <  tl  -  pl  &&  j  <  pl)  {
              
    if (patten.charAt(j)  ==  target.charAt(i + j))
                  j
    ++ ;
              
    else   {
                  j 
    =   0 ;
                  i
    ++ ;
              }

          }

          
    if (j  ==  pl)
              
    return  i;
          
    return   - 1 ;
      }

      
      
    public   static   void  main(String[] args) {
          String t 
    =   " 123456789 " ;
          String p 
    =   " 456 " ;
          SimpleMatch sm 
    =   new  SimpleMatch();
          System.out.println(sm.StringMatch(t, p));
      }

    }

    可以看见,这个算法(假定m>>n)的复杂度是O(mn),其中m是T的长度,n是P的长度。这种算法的缺陷是匹配过程中带有回溯——准确地说是T串存在回溯,也就是当匹配不成功的时候,之前进行的匹配完全变为无用功,所有的比较需要重新开始。

    3 KMP算法

    KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt提出的无回溯的字符串匹配算法,算法的核心思想就是设法在匹配失败的时候,尽量利用之前的匹配结果,消除T串的回溯问题。那么如何消除回溯呢?请看下面的例子:

    假设P=abacd,如果T=abax...,当从头开始匹配到字符c时,若c=x,显然,匹配过程继续;当c≠x时,按照朴素的匹配算法,T串会发生回溯,之后T串会从第2个字符b开始重新匹配,而不是从匹配失败的字符x开始继续。但是显然,对于上述的匹配过程,T串不需要从b开始重新匹配,它只需要从x开始和P的b字符继续匹配即可。如下:
    匹配过程:
    P=abacd
    T=abax....
         ^----比较到此处时发生匹配失败
    朴素匹配算法:
    P= abacd
    T=abax...
       ^----回溯到b,重新开始和P的匹配
    KMP算法:
    P=  abacd
    T=abax...
         ^----T串不回溯,从x处继续匹配

    现在的问题是,按照KMP算法,匹配失败的时候,P串需要重新调整位置,但是调整的依据是什么?Knuth等人发现,P调整位置的依据和P的构造有关,和T无关。具体来说,定义失效函数:f(j)=k,其中0<=k<=j,且k是使得p0p1...pk-1 = pj-k+1pj-k+2...pj成立的最大整数。建立失效函数的算法如下:
    public void Build() {
     if(pattern == null)
      throw new Exception("KMP Exception : null pattern");
     array = new int[pattern.Length];
     int i = 0, s = pattern.Length;
     if(s > 1)
      array[0] = 0;
     for(i = 1; i < s; i++) {
      if(pattern[i] == pattern[array[i - 1]])
       array[i] = array[i - 1] + 1;
      else
       array[i] = 0;
     }
    }

    匹配过程如下:
    public int Match(String target, int start) {
     if(array == null || pattern == null || target == null)
      return -1;
     int target_index = start;
     int pattern_index = 0;
     int token_length = target.Length;
     int pattern_length = pattern.Length;
     while(target_index < token_length && pattern_index < pattern_length) {
      if(target[target_index] == pattern[pattern_index]) {
       target_index++;
       pattern_index++;
      } else {
       if(pattern_index == begin)
        target_index++;
       else
        pattern_index = array[pattern_index - 1];
      }
     }
     if(pattern_index == pattern_length)
      return target_index - pattern_length;
     return -1;
    }

    4 支持通配符?和*的KMP算法

    KMP算法虽然能够进行字符串匹配,但是,在实践中字符串匹配往往还要支持通配符,MS系统中最常见的通配符是?和*。其中,?可以代表一个字符(不能没有),*可以代表任意多个字符(可以为空)。经典的KMP算法针对通配符是无能为力的,但是经过简单的改造,KMP算法也可以识别通配符。

    首先是?,根据?的功能,?表示任意字符,也就是说在匹配过程中,?永远匹配成功。因此对匹配函数的修改十分简单:
    ...
     while(target_index < token_length && pattern_index < pattern_length) {
      if(target[target_index] == pattern[pattern_index]|| pattern[pattern_index] == '?') {
       target_index++;
       pattern_index++;
      } else {
    ...
    建立失效函数的过程和匹配过程类似,修改如下:
    ...
     for(i = 1; i < s; i++) {
      if(pattern[i] == pattern[array[i - 1]]|| pattern[i] == '?' || pattern[array[i - 1]] == '?')
       array[i] = array[i - 1] + 1;
    ...

    本质上,?并没有修改算法,而仅仅修改了匹配规则——遇到?则一定匹配。然而*与此不同,*的作用是匹配任意多个字符,显然我们不能简单的修改匹配过程而满足要求。如果我们重新思考*的作用,我们会发现*的另一个作用就是分割P串,即如果P=P1*P2,那么与其说*代表匹配任意多个字符,不如说P的匹配条件是在匹配P1子串后再匹配P2子串。

    现在回顾失效函数的作用,如果当匹配到P的j+1位时匹配失败,那么重新开始匹配的时候,P串的位置调整到f(j)位,直到P串的位置调整到0,则匹配重新开始。但当P=P1*P2,假如P1已经匹配成功,而在P2中发生匹配失败,那么P串要需要调整位置,但P串无论如何调整,此时也不应该调整到0,最多调整到P2的开始处,因为P1已经匹配,只需匹配P2即可。假如P=abcab*abcab,失效函数应该是(注意之前提到*的作用):
    a b c a b * a b c a b
    0 0 0 1 2 - 6 6 6 7 8

    因此,要想让KMP支持*,那么关键是要重新设计失效函数的建立算法,如下:
    public void Build() {
     if(pattern == null)
      throw new Exception("KMP Exception : null pattern");
     array = new int[pattern.Length];
     int i = 0, s = pattern.Length;
     if(s > 1)
      array[0] = 0;
     int begin = 0;
     for(i = 1; i < s; i++) {
      if(pattern[i] == '*') {
       array[i] = i;
       begin = i + 1;
      } else if(pattern[i] == pattern[array[i - 1]] || pattern[i] == '?' || pattern[array[i - 1]] == '?')
       array[i] = array[i - 1] + 1;
      else
       array[i] = begin;
     }

    算法中begin表示每段字符串的开始位置。此外,匹配过程也应该进行相应的修改,因为字符*对于匹配没有任何帮助,它属于占位符,因此需要跳过,匹配算法如下:
    public int Match(String target, int start) {
     if(array == null || pattern == null || target == null)
      return -1;
     int target_index = start;
     int pattern_index = 0;
     int token_length = target.Length;
     int pattern_length = pattern.Length;
     int begin = 0;
     while(target_index < token_length && pattern_index < pattern_length) {
      if(pattern[pattern_index] == '*') {
       begin = pattern_index + 1;
       pattern_index++;
      } else if(target[target_index] == pattern[pattern_index] || pattern[pattern_index] == '?') {
       target_index++;
       pattern_index++;
      } else {
       if(pattern_index == begin)
        target_index++;
       else
        pattern_index = array[pattern_index - 1];
      }
     }
     if(pattern_index == pattern_length)
      return target_index - pattern_length + begin;
     return -1;
    }

    5 正则语言和确定状态自动机

    一个数字逻辑的问题:设计一个识别11011的电路,解这个问题的关键就是设计出这个电路的DFA,如下:

    仔细看看这个状态机,是不是和KMP的算法有几分类似呢?这并不是巧合,因为KMP算法中的失效函数总可以等价的转化为一个DFA。当然KMP的DFA远比识别11011的DFA要复杂,原因在于KMP接受的输入是全体字符集合,识别11011的DFA只接受0和1这两个输入。我们知道,一个正则语言和一个DFA是等价的,而KMP计算失效函数的算法,实际上等价于求DFA的过程,f(j)的值实际上表明状态j+1接受到不正确的字符时应该回溯到的状态(注意此时输入流并没有前进)。普通的字符串都能看成是一个正则语言,含有通配符?和*的字符串也可以等价的转换为一个正则表达式。但是,正则语言的集合远比KMP算法所能支持的模式集合的更大,期间原因还是刚才提过的输入问题。试想P=p1p2...pn,当匹配到pj的时候,如果下一个输入字符正是pj,那么状态机进入下一个状态,如果不是pj,那么状态机按照实效函数的指示转移到状态f(j-1),也就是说KMP状态机的每个状态只能根据输入是否为pj来进行转移。而正则表达式所对应的状态机则有所不同,如果正则语言L=l1l2...ln,假设这些都是字母,当匹配到lj位的时候,如果下一个输入字符正是lj,那么状态机进入下一个状态,否则它还可以根据输入的值进行转移,例如lj=c1时转换到状态x,lj=c2时状态转换到y等等。

    6 结语

    字符串匹配问题是老问题了,并没有太多新意可言,只不过虽然KMP算法十分简单,但它的内在含义还是十分深刻的。横向比较KMP、DFA和正则语言、正则表达式我们会发现,它们之间存在很多的关联,而这种比较也有利于我们更好的理解这些算法,或者改进这些算法。最后说一句,试图利用目前的框架使得KMP算法支持全部种类的通配符(对应于正则表达式就是x?、x*、x+、{m,n}等等)是不可能,而我们也不需要这么做,因为我们还有正则表达式嘛。

    展开全文
  • 主要介绍了使用C语言解决字符串匹配问题的方法,包括一道实例练习题,需要的朋友可以参考下
  • 主要介绍了C++中用栈来判断括号字符串匹配问题的实现方法,是一个比较实用的算法技巧,包含了关于栈的基本操作,需要的朋友可以参考下
  • 字符串匹配问题:输入一个字符串,计算其中包含的连续给定的子字符串的个数。例如输入字符串“ EFABCABCABCDABCDD ” , 给定子字符串“ ABC” ,输出是 3 。

    字符串匹配问题:输入一个字符串,计算其中包含的连续给定的子字符串的个数。

    例如输入字符串“ EFABCABCABCDABCDD ” , 给定子字符串“ ABC” ,输出是 3

    函数原型: int countsub( char *str, char *subs ) 。

    参数说明: str 保存输入的字符串的首地址, subs 保存需要统计的子字符串的首地址。

    返回值:包含的连续子字符串的个数


    分析:根据题意我们主要需要解决两个问题:
    1.如何去找到原字符串中的子字符串
    2.原字符串中“连续”的子字符串个数

    #include<stdio.h>
    
    int countsub( char *str, char *ss )
    {
        int count = 0, i = 0; 
        //count用来计算子字符串的个数,i用来计算连续的子字符串个数
        char *p = str, *q = ss;
        while( *p != '\0')
        {   
            q = ss; //每次都要初始化q指针,让它指向ss的第一个元素
            if(*p == *q)//判断p,q指针指向的元素是否相等
            {
                while( *p++ == *q++ )//判断相等并且p,q向后移一位
                {
                    if( *q == '\0')//当q指向最后'\0'时,就初始化q
                    {
                        q = ss;
                        count++;
                        //并且说明原字符串含有一个子字符串 count+1
                    }
                }
                if( i <= count)
                //这里是判断所求子字符串个数是否为最多的一个
                {
                    i = count;
                    count = 0;   
                }
            }
            else  //如果p,q指向的元素不同,p向后移一位
                p++;
        } 
    
        return i;  //返回i 的值
    }
    int main()
    {   
        char s1[1000] = {0}, s2[100] = {0};
        gets(s1);  //输入原字符串
        gets(s2);  //输入子字符串
    
        printf("%d\n", countsub( s1, s2 ));
    
        return 0;
    }
    

    展开全文
  • python的括号嵌套字符串匹配问题

    千次阅读 2019-03-09 17:26:48
    python的括号嵌套字符串匹配问题 首先,先简述一下我遇到的问题: 在做新闻页面爬虫时,所获得数据是如下的一串字符,其json字符串位于artiList()当中,所以我的目的表是将json数据通过 python的正则表达式提取出来...

    python的括号嵌套字符串匹配问题

    首先,先简述一下我遇到的问题:

    • 在做新闻页面爬虫时,所获得数据是如下的一串字符,其json字符串位于artiList()当中,所以我的目的表是将json数据通过
      python的正则表达式提取出来

    artiList({“BD29LPUBwangning”:[{“liveInfo”:null,“docid”:“E9RB5B5V0001875N”,“source”:“中国新闻网”,“title”:“钟山:民营企业已经成为中国对外>贸易的主力军”,“priority”:60,“hasImg”:1,“url”:“http:/3g.163.com/news/19/0309/15/E9RB5B5V0001875N.html”,“commentCount”:0,“imgsrc3gtype”:“1”,“stitle”:"",“digest”:“中新社北京3月9日电中国商务部部长钟山9日在北京表示,今年将”,“imgsrc”:“http:/cms-bucket.ws.126.net/2019/03/09/2adcf4582d8d4f0b8d0da5c781b49cb0.png”,“ptime”:“2019-03-09 15:48:12”}]})

    首先,我直接使用

       re.findall(r'[(](.*?)[)]', string)
    

    可以正常提取,但是一旦字符里出现(),则提取失败,如:

    (中国)商务部部长钟山9日在(北京)表示

    上述代码只能匹配到第一个" ) "就停止了

    经过改进

       p1 = re.compile(r'[(](.*)[)]', re.S)
       string1 = re.findall(p1, string)
    

    或者是

       re.findall('(?<=\().*(?<!\))', string)
    

    如上代码可以成功实现需求。

    解释一下:

    1. 正则匹配串前加了r就是为了使得里面的特殊符号不用写反斜杠了。

    2. [ ]具有去特殊符号的作用,也就是说 [(] 里的 ( 只是平凡的括号

    3. 正则匹配串里的()是为了提取整个正则串中符合括号里的正则的内容

    4. .是为了表示除了换行符的任一字符。*克林闭包,出现0次或无限次。

    5. 加了?是最小匹配,不加是贪婪匹配。

    6. re.S是为了让.表示除了换行符的任一字符。

    PS:这里再为大家提供2款非常方便的正则表达式工具供大家参考使用:

    1. JavaScript正则表达式在线测试工具:
      http://tools.jb51.net/regex/javascript

    2. 正则表达式在线生成工具:
      http://tools.jb51.net/regex/create_reg

    展开全文
  • 带通配符的字符串匹配问题

    千次阅读 2014-06-04 11:05:38
    字符串匹配问题,给定一串字符串,按照指定规则对其进行匹配,并将匹配的结果保存至output数组中,多个匹配项用空格间隔,最后一个不需要空格。 要求: 匹配规则中包含通配符?和*,其中?表示匹配任意一个...

    1. 字符串匹配问题,给定一串字符串,按照指定规则对其进行匹配,并将匹配的结果保存至output数组中,多个匹配项用空格间隔,最后一个不需要空格。


      要求:


    2. 匹配规则中包含通配符?和*,其中?表示匹配任意一个字符,*表示匹配任意多个(>=0)字符。
    3. 匹配规则要求匹配最大的字符子串,例如a*d,匹配abbdd而非abbd,即最大匹配子串。
    4. 匹配后的输入串不再进行匹配,从当前匹配后的字符串重新匹配其他字符串。


      请实现函数:


        char* my_find(char input[], char rule[])


      举例说明:



      注意事项:

      1. 自行实现函数my_find,勿在my_find函数里夹杂输出,且不准用C、C++库,和Java的String对象;

      2. 请注意代码的时间,空间复杂度,及可读性,简洁性;

      3. input=aaa,rule=aa时,返回一个结果aa,即可。

       

       

      解法一


      本题与上述第三十章的题不同,上题字符串转换成整数更多考察对思维的全面性和对细节的处理,本题则更多的是编程技巧。闲不多说,直接上代码:


      //copyright@cao_peng 2013/4/23
      int str_len(char *a)
      {
         
      //字符串长度
         
      if (a == 0)
          {
             
      return 0;
          }
         
      char *t = a;
         
      for (; *t; ++t)
              ;
         
      return (int) (t - a);
      }

      void str_copy(char *a, const char *b, int len)
      {
         
      //拷贝字符串 a = b
         
      for (; len > 0; --len, ++b, ++a)
          {
             
      *a = *b;
          }
         
      *a = 0;
      }

      char *str_join(char *a, const char *b, int lenb)
      {
         
      //连接字符串 第一个字符串被回收
         
      char *t;
         
      if (a == 0)
          {
              t
      = (char *) malloc(sizeof(char) * (lenb + 1));
              str_copy(t, b, lenb);
             
      return t;
          }
         
      else
          {
             
      int lena = str_len(a);
              t
      = (char *) malloc(sizeof(char) * (lena + lenb + 2));
              str_copy(t, a, lena);
             
      *(t + lena) = ' ';
              str_copy(t
      + lena + 1, b, lenb);
              free(a);
             
      return t;
          }
      }

      int canMatch(char *input, char *rule)
      {
         
      // 返回最长匹配长度 -1表示不匹配
         
      if (*rule == 0)
          {
             
      //已经到rule尾端
             
      return 0;
          }
         
      int r = -1 , may;
         
      if (*rule == '*')
          {
              r
      = canMatch(input, rule + 1);  // *匹配0个字符
             
      if (*input)
              {
                  may
      = canMatch(input + 1, rule);  // *匹配非0个字符
                 
      if ((may >= 0) && (++may > r))
                  {
                      r
      = may;
                  }
              }
          }
         
      if (*input == 0)
          {
             
      //到尾端
             
      return r;
          }
         
      if ((*rule == '?') || (*rule == *input))
          {
              may
      = canMatch(input + 1, rule + 1);
             
      if ((may >= 0) && (++may > r))
              {
                  r
      = may;
              }
          }
         
      return r;
      }

      char * my_find(char input[], char rule[])
      {
         
      int len = str_len(input);
         
      int *match = (int *) malloc(sizeof(int) * len);  //input第i位最多能匹配多少位 匹配不上是-1
         
      int i, max_pos = - 1;
         
      char *output = 0;

         
      for (i = 0; i < len; ++i)
          {
              match[i]
      = canMatch(input + i, rule);
             
      if ((max_pos < 0) || (match[i] > match[max_pos]))
              {
                  max_pos
      = i;
              }
          }
         
      if ((max_pos < 0) || (match[max_pos] <= 0))
          {
             
      //不匹配
              output
      = (char *) malloc(sizeof(char));
             
      *output = 0;   // \0
             
      return output;
          }
         
      for (i = 0; i < len;)
          {
             
      if (match[i] == match[max_pos])
              {
                 
      //找到匹配
                  output
      = str_join(output, input + i, match[i]);
                  i
      += match[i];
              }
             
      else
              {
                 
      ++i;
              }
          }
          free(match);
         
      return output;
      }

       

       

      解法二、动态规划


      本题也可以直接写出DP(Dynamic Programming, 动态规划)方程,如下代码所示:


      //copyright@chpeih 2013/4/23
      char* my_find(char input[], char rule[])
      {
         
      //write your code here
         
      int len1, len2;
         
      for (len1 = 0; input[len1]; len1++);
         
      for (len2 = 0; rule[len2]; len2++);
         
      int MAXN = len1 > len2 ? (len1 + 1) : (len2 + 1);
         
      int  **dp;

         
      //dp[i][j]表示字符串1和字符串2分别以i j结尾匹配的最大长度
         
      //记录dp[i][j]是由之前那个节点推算过来  i*MAXN+j
          dp
      = new int *[len1 + 1];
         
      for (int i = 0; i <= len1; i++)
          {
              dp[i]
      = new int[len2 + 1];

          }

          dp[
      0][0] = 0;
         
      for (int i = 1; i <= len2; i++)
              dp[
      0][i] = -1;
         
      for (int i = 1; i <= len1; i++)
              dp[i][
      0] = 0;

         
      for (int i = 1; i <= len1; i++)
          {
             
      for (int j = 1; j <= len2; j++)
              {
                 
      if (rule[j - 1] == '*')
                  {
                      dp[i][j]
      = -1;
                     
      if (dp[i - 1][j - 1] != -1)
                      {
                          dp[i][j]
      = dp[i - 1][j - 1] + 1;

                      }
                     
      if (dp[i - 1][j] != -1 && dp[i][j] < dp[i - 1][j] + 1)
                      {
                          dp[i][j]
      = dp[i - 1][j] + 1;
                      }
                  }
                 
      else if (rule[j - 1] == '?')
                  {
                     
      if (dp[i - 1][j - 1] != -1)
                      {
                          dp[i][j]
      = dp[i - 1][j - 1] + 1;

                      }
                     
      else dp[i][j] = -1;
                  }
                 
      else
                  {
                     
      if (dp[i - 1][j - 1] != -1 && input[i - 1] == rule[j - 1])
                      {
                          dp[i][j]
      = dp[i - 1][j - 1] + 1;
                      }
                     
      else dp[i][j] = -1;
                  }
              }
          }

         
      int m = -1;//记录最大字符串长度
         
      int *ans = new int[len1];
         
      int count_ans = 0;//记录答案个数
         
      char *returnans = new char[len1 + 1];
         
      int count = 0;
         
      for (int i = 1; i <= len1; i++)
             
      if (dp[i][len2] > m)
              {
                  m
      = dp[i][len2];
                  count_ans
      = 0;
                  ans[count_ans
      ++] = i - m;
              }
             
      else if (dp[i][len2] != -1 && dp[i][len2] == m)
              {
                  ans[count_ans
      ++] = i - m;
              }

         
      if (count_ans != 0)
          {
             
      int len = ans[0];
             
      for (int i = 0; i < m; i++)
              {
                  printf(
      "%c", input[i + ans[0]]);
                  returnans[count
      ++] = input[i + ans[0]];
              }
             
      for (int j = 1; j < count_ans; j++)
              {
                  printf(
      " ");
                  returnans[count
      ++] = ' ';
                  len
      = ans[j];
                 
      for (int i = 0; i < m; i++)
                  {
                      printf(
      "%c", input[i + ans[j]]);
                      returnans[count
      ++] = input[i + ans[j]];
                  }
              }
              printf(
      "\n");
              returnans[count
      ++] = '\0';
          }

         
      return returnans;
      }

       

      Pasted from <https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.03.md>

       

    展开全文
  • 无顺序约束的字符串匹配问题

    千次阅读 2016-04-06 19:26:22
    字符串A较长,字符串B较短,如何以最短时间判断出B里的所有字母在A中都有:?B⊆A?B\subseteq A 举例: A=abcdeabcdft,B=dcea,返回ture ...(有顺序约束的字符串匹配问题,请大家参考KMP算法)
  • 字符串匹配问题,给定一串字符串,按照指定规则对其进行匹配,并将匹配的结果保存至output数组中,多个匹配项用空格间隔,最后一个不需要空格。 要求: 1. 匹配规则中包含通配符?和*,其中?表示匹配任意一个字符,*...
  • 用java实现字符串匹配问题

    千次阅读 2020-06-29 12:30:47
    考题:判断字符串 a 是否包含字符串 b,这里称 a 为文本串,b 为模式串。 代码如下: import java.util.Scanner; public class demo { /** * 判断是否匹配 * * @param target 目标文本串 * @param mode 模式...
  • 子串和长是不固定的,任意输入,最终显示匹配或不匹配
  • 题目是:输入两个字符串,输出字符串1中与字符串2最先匹配的内容,字符串2中可包含?,?可代表任何字符。已知字符串2不会全为?。 输入输出格式:输入:abcdefabcdeg,a?c??f 输出:abcdef 下述代码可...
  • ,{},判断输入的字符串中括号是否匹配。如果括号有互相包 含的形式,从内到外必须是<>,(),[],{},例如。输入: [()] 输出:YES,而输入([]),([)]都应该 输出 NO。 输入 第一行为一个整数 n,表示以下有多少个由...
  • 字符串匹配问题(BF算法、KMP算法)

    千次阅读 2018-11-17 10:18:42
    给定两个字符串S和T,在主串S中查找子串T的过程称为串匹配,T称为模式。 BF算法(朴素模式匹配): BF算法思想:  就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和...
  • 判断文件中是否存在某一字符串,若存在则退出,若不存在则添加???求用c编写的代码,,,各位大虾帮帮忙,万分感谢!!!!!
  • Rabin-Karp算法:字符串匹配问题

    万次阅读 多人点赞 2018-11-13 05:40:22
    SubString Pattern Matching(字符串匹配/查重) Rabin-Karp是用来解决字符串匹配(查重)的问题的。该问题的严谨定义如下: Input:一段字符串t,和一个字符串p Output:如果t中含有p,那么输出yes,如果没有,...
  • 含通配符的字符串匹配问题

    千次阅读 2015-06-30 16:07:00
    给定两个字符串,求字符串2,在字符串1中的最先匹配结果。字符串2中 可以存在’*’符号,且该符号可以代表任意字符,即字符串2中存在通配符。 例如:输入:abcdefghabef,a*f 输出:abcdef#include<iostream>
  • 本文通过简单的事例阐述字符串对比的算法思想,并用java给予实现。该算法可以用于求两个字符串的子串、最大子串等。
  • 1355:字符串匹配问题(strs)

    千次阅读 2018-07-26 12:58:34
    ,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式,从内到外必须是&lt;&gt;,(),[],{},例如。输入: [()] 输出:YES,而输入([]),([)]都应该输出NO。 【输入】 第一行为一个整数n,表示以下...
  • 题目:输入两字符串S,T,输出在S中存在但在T中不存在的字符存储到新的字符串中, 并保持其在字符串S中的顺序,然后在屏幕上显示新的字符串的内容。 ====================================================
  • 10 正则表达式匹配 ...匹配应该覆盖整个字符串 (s) ,而不是部分字符串。 说明: s 可能为空,且只包含从 a-z 的小写字母。 p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。 示例 1: 输入:...
  • 从键盘输入字符文件名以及子串,用改进KMP算法在字符文件中实现子串查找。要求程序输出子串的改进nextval数组元素值以及子串在文件中成功匹配的次数(查找失败输出成功匹配次数为0),c++语言
  • ,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式,从内到外必须是<>,(),[],{},例如。输入: [()] 输出:YES,而输入([]),([)]都应该输出NO。 【输入】 第一行为一个整数n,表示以下有多少个...
  • 给出如下两字符串: String str1=“lovilovilovloveiloveyou”; String str2=“ilove”; 要求从 str1 中找出是否存在目标字符串 str2,如果有,返回第一次出现的首字符下标,没有返回-1. 暴力匹配算法: 思路分析: ...
  • 判断包含通配符的匹配字符串是否完全匹配输入的字符串匹配字符串中包含的通配符仅有‘ * ’和‘?’,且通配符不会连续出现 。(要求完全匹配,而不是包含) 其中,通配符‘ * ’:代替 0 个或多个字符,通配符‘ ...
  • 下面代码列举了普通字符串匹配算法和KMP算法。KMP算法原理见算法导论第32章。代码中有简单的注释可以帮助理解: #include #include using namespace std; #define MAX 10000 //KMP算法时间复杂度为O(n+m),其中...
  • 正则表达式定义了字符串的模式。 正则表达式可以用来搜索、编辑或处理文本。 正则表达式并不仅限于某一种语言,但是在每种语言中有细微的差别。 Java正则表达式和Perl的是最为相似的。 java.util.regex包主要...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 437,464
精华内容 174,985
关键字:

字符串匹配问题