正则表达式匹配字符串匹配非_匹配模式和字符串而不使用正则表达式

正则表达式匹配字符串匹配非

Description: 描述：

This is a standard interview problem to match a pattern and string without using regular expressions using backtracking algorithm.

这是在不使用正则表达式的情况下使用回溯算法来匹配模式和字符串的标准采访问题。

Problem statement: 问题陈述：

A string and a pattern are given to you. You have to match the pattern and string without using regular expression.

会给您一个字符串和一个模式。 您必须在不使用正则表达式的情况下匹配模式和字符串。

Input:
    Test Case T.

    T no. of lines with the strings and patterns.
    
    E.g.
    3
    abcbbabc
    aba
    Includehelp
    aa
    GreenRedYellowRed
    GRYR
    
    Output:
    Print the character with their respectively representation.
           

Example 例

T= 3

    Input:
    String  : abcbbabc
    Pattern: aba
    
    Output:
    a →  abc
    b →  bb
    
    Input:
    String  : Includehelp
    Pattern: aa
    
    Output:
    Matching not possible.
    
    Input:
    String  : GreenRedYellowRed
    Pattern: GRYR
    
    Output:
    G → Green
    R → Red
    Y → Yellow
           

Explanation with example: 举例说明：

Match a string with a pattern is a problem of combination and we will solve this problem with the backtracking process.

将字符串与模式匹配是组合的问题，我们将通过回溯过程解决此问题。

To solve this problem, we will follow this algorithm,

为了解决这个问题，我们将遵循以下算法，

match(string ,pattern ,string_pointer,patter_pointer,map,set):
    if(string_pointer equals to the null pointer of the string and 
    pattern_pointer equals to the null pointer of the pattern) Then
        return true
    end if
    if(string_pointer equals to the null pointer of the string or 
    pattern_pointer equals to the null pointer of the pattern) Then
        return false
    end if
    for i-> string_pointer+1 to string_length
        taking a substring of the original from string_pointer to i
        if(the substring is not in map)Then
            if(pattern is already present in the set) Then
                continue
            end if
            insert the pair of substring and the corresponding pattern into the map
            insert the pattern into the set
        end if
        else if(the substring is already map) Then
            if(substring's corresponding pattern is not matched with
            the pattern which is at the patter_pointer) Then
            continue;
            end if
        end if
        if(call the pattern for string_pointer+1 and patter_pointer+1)
            return true;
    end for
    return false;
           

C++ implementation: C ++实现：

#include <bits/stdc++.h>
using namespace std;

bool match(string str, string pat, int str_pos, int pat_pos, map<string, char>& m, set<char>& se)
{
    if (str_pos == str.length() && pat_pos == pat.length()) {
        return true;
    }
    if (str_pos >= str.length() || pat_pos == pat.length())
        return false;
    int flag = 0;
    for (int i = str_pos + 1; i <= str.length(); i++) {
        string s = str.substr(str_pos, (i - str_pos));
        //if the substring is not present in the map
        if (m.find(s) == m.end()) {
            //if the pattern is already has a string
            if (se.find(pat[pat_pos]) != se.end())
                continue;
            m.insert(make_pair(s, pat[pat_pos]));
            se.insert(pat[pat_pos]);
            flag = 1;
        }
        //if the substring is already present into the map
        else if (m.find(s) != m.end()) {
            //if the corresponding pattern is not match with the current pattern
            if (m[s] != pat[pat_pos]) {
                continue;
            }
        }
        if (match(str, pat, i, pat_pos + 1, m, se))
            return true;
        if (flag) {
            m.erase(s);
            se.erase(pat[pat_pos]);
            flag = 0;
        }
    }
    return false;
}

void match_the_pattern(string str, string pat)
{
    map<string, char> m;
    int str_pos = 0;
    int pat_pos = 0;
    set<char> s;
    if (match(str, pat, str_pos, pat_pos, m, s)) {
        map<string, char>::iterator it;
        for (it = m.begin(); it != m.end(); it++) {
            cout << it->second << " -> " << it->first << endl;
        }
    }
    else {
        cout << "Matching not possible" << endl;
    }
}

int main()
{
    int t;

    cout << "Test Case : ";
    cin >> t;

    while (t--) {
        string str, pat;
        cout << "Enter the String : ";
        cin >> str;
        cout << "Enter the pattern : ";
        cin >> pat;
        match_the_pattern(str, pat);
    }

    return 0;
}
           

Output 输出量

Test Case : 3
Enter the String : abcbbabc
Enter the pattern : aba
a -> abc
b -> bb
Enter the String : includehelp
Enter the pattern : aa
Matching not possible
Enter the String : GreenRedYellowRed
Enter the pattern : GRYR
G -> Green
R -> Red
Y -> Yellow
           

翻译自: https://www.includehelp.com/icp/match-a-pattern-and-string-without-using-regular-expressions.aspx

正则表达式匹配字符串匹配非