匹配表达式，其中模式中的单个特殊字符可以匹配一个或多个字符-yiteyi-C++库

给定两个字符串，其中一个是模式，另一个是搜索表达式。搜索表达式包含“#”。 #的工作方式如下：

null

A#与一个或多个字符匹配。
A#在找到模式匹配之前匹配所有字符。例如，如果pat=“A#B”，文本为“accb”，那么#将仅与“CC”匹配，并且认为找不到模式。

例如：

Input  : str = "ABABABA"          pat = "A#B#A" Output : yesInput  : str = "ABCCB"          pat = "A#B"Output : yesInput  : str = "ABCABCCE"          pat = "A#C#"Output : yesInput  : str = "ABCABCCE"          pat = "A#C"Output : no

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们可以观察到，每当我们遇到“γ”时，我们必须考虑多个字符，直到该模式的下一个字符将不等于给定字符串的当前字符。首先，我们检查模式的当前字符是否等于“#”- a）如果不是，则检查字符串和模式的当前字符是否相同，如果相同，则递增两个计数器，否则仅从这里返回false。无需进一步检查。 b）如果是，那么我们必须找到文本中与模式的下一个字符匹配的字符位置。

C++

                         // C++ program for pattern matching                       
                         // where a single special character                       
                         // can match one more characters                       
                         #include<bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         // Returns true if pat matches with text                       
                         int                                     regexMatch(string text, string pat)                       
                         {                       
                                                 int                                     lenText = text.length();                       
                                                 int                                     letPat = pat.length();                       
           
                                                 // i is used as an index in pattern                       
                                                 // and j as an index in text                       
                                                 int                                     i = 0, j = 0;                       
           
                                                 // Traverse through pattern                       
                                                 while                                     (i < letPat)                       
                                                 {                       
                                                 // If current character of                       
                                                 // pattern is not '#'                       
                                                 if                                     (pat[i] !=                                     '#'                                     )                       
                                                 {                       
                                                 // If does not match with text                       
                                                 if                                     (pat[i] != text[j])                       
                                                 return                                     false                                     ;                       
           
                                                 // If matches, increment i and j                       
                                                 i++;                       
                                                 j++;                       
                                                 }                       
           
                                                 // Current character is '#'                       
                                                 else                       
                                                 {                       
                                                 // At least one character                       
                                                 // must match with #                       
                                                 j++;                       
           
                                                 // Match characters with # until                       
                                                 // a matching character is found.                       
                                                 while                                     (text[j] != pat[i + 1])                       
                                                 j++;                       
           
                                                 // Matching with # is over,                       
                                                 // move ahead in pattern                       
                                                 i++;                       
                                                 }                       
                                                 }                       
           
                                                 return                                     (j == lenText);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 string str =                                     "ABABABA"                                     ;                       
                                                 string pat =                                     "A#B#A"                                     ;                       
                                                 if                                     (regexMatch(str, pat))                       
                                                 cout <<                                     "yes"                                     ;                       
                                                 else                       
                                                 cout <<                                     "no"                                     ;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program for pattern matching                       
                         // where a single special character                       
                         // can match one more characters                       
           
                         import                                     java.util.*;                       
                         import                                     java.lang.*;                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                                 // Returns true if pat                       
                                                 // matches with text.                       
                                                 public                                     static                                     boolean                                     regexMatch                       
                                                 (String text, String pat)                       
                                                 {                       
                                                 int                                     lenText = text.length();                       
                                                 int                                     lenPat = pat.length();                       
                                   
                                                 char                                     [] Text = text.toCharArray();                       
                                                 char                                     [] Pat = pat.toCharArray();                       
                                   
                                                 // i is used as an index in pattern                       
                                                 // and j as an index in text.                       
                                                 int                                     i =                                     0                                     , j =                                     0                                     ;                       
                                   
                                                 // Traverse through pattern                       
                                                 while                                     (i < lenPat)                       
                                                 {                       
                                                 // If current character of                       
                                                 // pattern is not '#'                       
                                                 if                                     (Pat[i] !=                                     '#'                                     )                       
                                                 {                       
                                                 // If does not match with text.                       
                                                 if                                     (Pat[i] != Text[j])                       
                                                 return                                     false                                     ;                       
                                   
                                                 // If matches, increment i and j                       
                                                 i++;                       
                                                 j++;                       
                                                 }                       
                                   
                                                 // Current character is '#'                       
                                                 else                       
                                                 {                       
                                                 // At least one character                       
                                                 // must match with #                       
                                                 j++;                       
                                   
                                                 // Match characters with # until                       
                                                 // a matching character is found.                       
                                                 while                                     (Text[j] != Pat[i +                                     1                                     ])                       
                                                 j++;                       
                                   
                                                 // Matching with # is over,                       
                                                 // move ahead in pattern                       
                                                 i++;                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     (j == lenText);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 String str =                                     "ABABABA"                                     ;                       
                                                 String pat =                                     "A#B#A"                                     ;                       
                                                 if                                     (regexMatch(str, pat))                       
                                                 System.out.println(                                     "yes"                                     );                       
                                                 else                       
                                                 System.out.println(                                     "no"                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Mr. Somesh Awasthi                       

Python3

                         # Python3 program for pattern matching                       
                         # where a single special character                       
                         # can match one more characters                       
           
                         # Returns true if pat matches with                       
                         # text                       
                         def                                     regexMatch(text, pat):                       
           
                                                 lenText                                     =                                     len                                     (text)                       
                                                 letPat                                     =                                     len                                     (pat)                       
           
                                                 # i is used as an index in                       
                                                 # pattern and j as an index                       
                                                 # in text                       
                                                 i                                     =                                     0                       
                                                 j                                     =                                     0                       
           
                                                 # Traverse through pattern                       
                                                 while                                     (i < letPat):                       
           
                                                 # If current character of                       
                                                 # pattern is not '#'                       
                                                 if                                     (pat[i] !                                     =                                     '#'                                     ):                       
           
                                                 # If does not match with                       
                                                 # text                       
                                                 if                                     (pat[i] !                                     =                                     text[j]):                       
                                                 return                                     False                       
           
                                                 # If matches, increment                       
                                                 # i and j                       
                                                 i                                     +                                     =                                     1                       
                                                 j                                     +                                     =                                     1                       
           
                                                 # Current character is '#'                       
                                                 else                                     :                       
           
                                                 # At least one character                       
                                                 # must match with #                       
                                                 j                                     +                                     =                                     1                       
           
                                                 # Match characters with # until                       
                                                 # a matching character is found.                       
                                                 while                                     (text[j] !                                     =                                     pat[i                                     +                                     1                                     ]):                       
                                                 j                                     +                                     =                                     1                       
           
                                                 # Matching with # is over,                       
                                                 # move ahead in pattern                       
                                                 i                                     +                                     =                                     1                       
           
                                                 return                                     (j                                     =                                     =                                     lenText)                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 st                                     =                                     "ABABABA"                       
                                                 pat                                     =                                     "A#B#A"                       
                                                 if                                     (regexMatch(st, pat)):                       
                                                 print                                     (                                     "yes"                                     )                       
                                                 else                                     :                       
                                                 print                                     (                                     "no"                                     )                       
           
                         # This code is contributed by Chitranayal                       

C#

                         // C# program for pattern matching                       
                         // where a single special character                       
                         // can match one more characters                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                                 // Returns true if pat                       
                                                 // matches with text.                       
                                                 public                                     static                                     bool                                     regexMatch                       
                                                 (String text, String pat)                       
                                                 {                       
                                                 int                                     lenText = text.Length;                       
                                                 int                                     lenPat = pat.Length;                       
                                   
                                                 char                                     []Text = text.ToCharArray();                       
                                                 char                                     []Pat = pat.ToCharArray();                       
                                   
                                                 // i is used as an index in pattern                       
                                                 // and j as an index in text.                       
                                                 int                                     i = 0, j = 0;                       
                                   
                                                 // Traverse through pattern                       
                                                 while                                     (i < lenPat)                       
                                                 {                       
                                                 // If current character                       
                                                 // of pattern is not '#'                       
                                                 if                                     (Pat[i] !=                                     '#'                                     )                       
                                                 {                       
                                                 // If does not match with text.                       
                                                 if                                     (Pat[i] != Text[j])                       
                                                 return                                     false                                     ;                       
                                   
                                                 // If matches, increment i and j                       
                                                 i++;                       
                                                 j++;                       
                                                 }                       
                                   
                                                 // Current character is '#'                       
                                                 else                       
                                                 {                       
                                                 // At least one character                       
                                                 // must match with #                       
                                                 j++;                       
                                   
                                                 // Match characters with # until                       
                                                 // a matching character is found.                       
                                                 while                                     (Text[j] != Pat[i + 1])                       
                                                 j++;                       
                                   
                                                 // Matching with # is over,                       
                                                 // move ahead in pattern                       
                                                 i++;                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     (j == lenText);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 String str =                                     "ABABABA"                                     ;                       
                                                 String pat =                                     "A#B#A"                                     ;                       
                                                 if                                     (regexMatch(str, pat))                       
                                                 Console.Write(                                     "yes"                                     );                       
                                                 else                       
                                                 Console.Write(                                     "no"                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by nitin mittal                       

PHP

                         <?php                       
                         // PHP program for pattern matching                       
                         // where a single special character                       
                         // can match one more characters                       
           
                         // Returns true if pat                       
                         // matches with text                       
                         function                                     regexMatch(                                     $text                                     ,                                     $pat                                     )                       
                         {                       
                                                 $lenText                                     =                                     strlen                                     (                                     $text                                     );                       
                                                 $letPat                                     =                                     strlen                                     (                                     $pat                                     );                       
           
                                                 // i is used as an index in pattern                       
                                                 // and j as an index in text                       
                                                 $i                                     = 0;                                     $j                                     = 0;                       
           
                                                 // Traverse through pattern                       
                                                 while                                     (                                     $i                                     <                                     $letPat                                     )                       
                                                 {                       
                                   
                                                 // If current character of                       
                                                 // pattern is not '#'                       
                                                 if                                     (                                     $pat                                     [                                     $i                                     ] !=                                     '#'                                     )                       
                                                 {                       
                                   
                                                 // If does not match with text                       
                                                 if                                     (                                     $pat                                     [                                     $i                                     ] !=                                     $text                                     [                                     $j                                     ])                       
                                                 return                                     false;                       
           
                                                 // If matches, increment i and j                       
                                                 $i                                     ++;                       
                                                 $j                                     ++;                       
                                                 }                       
           
                                                 // Current character is '#'                       
                                                 else                       
                                                 {                       
                                   
                                                 // At least one character                       
                                                 // must match with #                       
                                                 $j                                     ++;                       
           
                                                 // Match characters with # until                       
                                                 // a matching character is found.                       
                                                 while                                     (                                     $text                                     [                                     $j                                     ] !=                                     $pat                                     [                                     $i                                     + 1])                       
                                                 $j                                     ++;                       
           
                                                 // Matching with # is over,                       
                                                 // move ahead in pattern                       
                                                 $i                                     ++;                       
                                                 }                       
                                                 }                       
           
                                                 return                                     (                                     $j                                     ==                                     $lenText                                     );                       
                         }                       
           
                         // Driver code                       
                         $str                                     =                                     "ABABABA"                                     ;                       
                         $pat                                     =                                     "A#B#A"                                     ;                       
                         if                                     (regexMatch(                                     $str                                     ,                                     $pat                                     ))                       
                                                 echo                                     "yes"                                     ;                       
                         else                       
                                                 echo                                     "no"                                     ;                       
           
                         // This code is contributed by nitin mittal                       
                         ?>                       

Javascript

                         <script>                       
                         // Javascript program for pattern matching                       
                         // where a single special character                       
                         // can match one more characters                       
                                   
                                                 // Returns true if pat                       
                                                 // matches with text.                       
                                                 function                                     regexMatch(text,pat)                       
                                                 {                       
                                                 let lenText = text.length;                       
                                                 let lenPat = pat.length;                       
                                   
                                                 let Text = text.split(                                     ""                                     );                       
                                                 let Pat = pat.split(                                     ""                                     );                       
                                   
                                                 let i = 0, j = 0;                       
                                                 // Traverse through pattern                       
                                                 while                                     (i < lenPat)                       
                                                 {                       
                                                 // If current character of                       
                                                 // pattern is not '#'                       
                                                 if                                     (Pat[i] !=                                     '#'                                     )                       
                                                 {                       
                                                 // If does not match with text.                       
                                                 if                                     (Pat[i] != Text[j])                       
                                                 return                                     false                                     ;                       
                                   
                                                 // If matches, increment i and j                       
                                                 i++;                       
                                                 j++;                       
                                                 }                       
                                   
                                                 // Current character is '#'                       
                                                 else                       
                                                 {                       
                                                 // At least one character                       
                                                 // must match with #                       
                                                 j++;                       
                                   
                                                 // Match characters with # until                       
                                                 // a matching character is found.                       
                                                 while                                     (Text[j] != Pat[i + 1])                       
                                                 j++;                       
                                   
                                                 // Matching with # is over,                       
                                                 // move ahead in pattern                       
                                                 i++;                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     (j == lenText);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 let str =                                     "ABABABA"                                     ;                       
                                                 let pat =                                     "A#B#A"                                     ;                       
                                                 if                                     (regexMatch(str, pat))                       
                                                 document.write(                                     "yes"                                     );                       
                                                 else                       
                                                 document.write(                                     "no"                                     );                       
                                   
                                                 // This code is contributed by rag2127                       
                         </script>                       

输出：

yes

本文由 罗什尼·阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章