Рубрики

Подстановочный шаблон

При наличии текста и шаблона с подстановочными знаками реализуйте алгоритм сопоставления шаблонов с подстановочными знаками, который определяет, соответствует ли шаблон с подстановочными знаками тексту. Соответствие должно охватывать весь текст (не частичный текст).

Шаблон подстановки может включать символы «?» и '*'
'?' — соответствует любому отдельному символу
'*' — соответствует любой последовательности символов (включая пустую последовательность)

Например,

Text = "baaabab",
Pattern = “*****ba*****ab", output : true
Pattern = "baaa?ab", output : true
Pattern = "ba*a?", output : true
Pattern = "a*ab", output : false 

Каждое вхождение '?' символ в шаблоне подстановки может быть заменен любым другим символом, и каждое вхождение '*' с последовательностью символов, так что шаблон подстановки становится идентичным входной строке после замены.

Давайте рассмотрим любой символ в шаблоне.

Случай 1: символ «*»
Здесь возникают два случая

  1. Мы можем игнорировать символ '*' и переходить к следующему символу в шаблоне.
  2. Символ * соответствует одному или нескольким символам в тексте. Здесь мы перейдем к следующему символу в строке.

Случай 2: символ «?»
Мы можем игнорировать текущий символ в тексте и перейти к следующему символу в шаблоне и тексте.

Случай 3: персонаж не подстановочный
Если текущий символ в тексте совпадает с текущим символом в шаблоне, мы переходим к следующему символу в шаблоне и тексте. Если они не совпадают, шаблон подстановочного знака и текст не совпадают.

Мы можем использовать динамическое программирование для решения этой проблемы —
Пусть T [i] [j] равно true, если первые i символов в данной строке совпадают с первыми j символами шаблона.

Инициализация DP:

// both text and pattern are null
T[0][0] = true; 

// pattern is null
T[i][0] = false; 

// text is null
T[0][j] = T[0][j - 1] if pattern[j – 1] is '*'  

Отношение DP:

// If current characters match, result is same as 
// result for lengths minus one. Characters match
// in two cases:
// a) If pattern character is '?' then it matches  
//    with any character of text. 
// b) If current characters in both match
if ( pattern[j – 1] == ‘?’) || 
     (pattern[j – 1] == text[i - 1])
    T[i][j] = T[i-1][j-1]   
 
// If we encounter ‘*’, two choices are possible-
// a) We ignore ‘*’ character and move to next 
//    character in the pattern, i.e., ‘*’ 
//    indicates an empty sequence.
// b) '*' character matches with ith character in
//     input 
else if (pattern[j – 1] == ‘*’)
    T[i][j] = T[i][j-1] || T[i-1][j]  

else // if (pattern[j – 1] != text[i - 1])
    T[i][j]  = false 
 

Ниже приведена реализация вышеупомянутого подхода динамического программирования.

C ++

// C ++ программа для реализации подстановочного знака
// алгоритм сопоставления с образцом
#include <bits/stdc++.h>

using namespace std;

  
// Функция, которая соответствует входной строке с
// данный шаблон

bool strmatch(char str[], char pattern[],

              int n, int m)

{

    // пустой шаблон может совпадать только с

    // пустая строка

    if (m == 0)

        return (n == 0);

  

    // таблица поиска для сохранения результатов

    // подзадачи

    bool lookup[n + 1][m + 1];

  

    // initailze таблица поиска в false

    memset(lookup, false, sizeof(lookup));

  

    // пустой шаблон может совпадать с пустой строкой

    lookup[0][0] = true;

  

    // Только '*' может совпадать с пустой строкой

    for (int j = 1; j <= m; j++)

        if (pattern[j - 1] == '*')

            lookup[0][j] = lookup[0][j - 1];

  

    // заполняем таблицу снизу вверх

    for (int i = 1; i <= n; i++)

    {

        for (int j = 1; j <= m; j++)

        {

            // Два случая, если мы видим '*'

            // а) Мы игнорируем символ '*' и перемещаемся

            // к следующему символу в шаблоне,

            // т.е. '*' указывает на пустую последовательность.

            // b) символ '*' совпадает с ith

            // символ на входе

            if (pattern[j - 1] == '*')

                lookup[i][j] = lookup[i][j - 1] ||

                               lookup[i - 1][j];

  

            // Текущие символы считаются

            // соответствие в двух случаях

            // (а) текущим символом шаблона является '?'

            // (б) символы действительно совпадают

            else if (pattern[j - 1] == '?' ||

                    str[i - 1] == pattern[j - 1])

                lookup[i][j] = lookup[i - 1][j - 1];

  

            // Если символы не совпадают

            else lookup[i][j] = false;

        }

    }

  

    return lookup[n][m];

}

  

int main()

{

    char str[] = "baaabab";

    char pattern[] = "*****ba*****ab";

    // char pattern [] = "ba ***** ab";

    // char pattern [] = "ba * ab";

    // char pattern [] = "a * ab";

    // char pattern [] = "a ***** ab";

    // char pattern [] = "* a ***** ab";

    // char pattern [] = "ba * ab ****";

    // char pattern [] = "****";

    // char pattern [] = "*";

    // char pattern [] = "aa? ab";

    // char pattern [] = "b * b";

    // char pattern [] = "a * a";

    // char pattern [] = "baaabab";

    // char pattern [] = "? baaabab";

    // char pattern [] = "* baaaba *";

  

    if (strmatch(str, pattern, strlen(str),

                         strlen(pattern)))

        cout <<    "Yes" << endl;

    else

        cout << "No" << endl;

  

    return 0;

}

Джава

// Java-программа для реализации подстановочного знака
// алгоритм сопоставления с образцом

import java.util.Arrays;

public class GFG{     

       

    // Функция, которая соответствует входной строке с

    // данный шаблон

    static boolean strmatch(String str, String pattern,

                                 int n, int m)

    {

        // пустой шаблон может совпадать только с

        // пустая строка

        if (m == 0)

            return (n == 0);

       

        // таблица поиска для сохранения результатов

        // подзадачи

        boolean[][] lookup = new boolean[n + 1][m + 1];

       

        // initailze таблица поиска в false

        for(int i = 0; i < n + 1; i++)

            Arrays.fill(lookup[i], false);

          

       

        // пустой шаблон может совпадать с пустой строкой

        lookup[0][0] = true;

       

        // Только '*' может совпадать с пустой строкой

        for (int j = 1; j <= m; j++)

            if (pattern.charAt(j - 1) == '*')

                lookup[0][j] = lookup[0][j - 1];

       

        // заполняем таблицу снизу вверх

        for (int i = 1; i <= n; i++)

        {

            for (int j = 1; j <= m; j++)

            {

                // Два случая, если мы видим '*'

                // а) Мы игнорируем символ * и перемещаемся

                // к следующему символу в шаблоне,

                // т.е. '*' указывает на пустую последовательность.

                // b) символ '*' совпадает с ith

                // символ на входе

                if (pattern.charAt(j - 1) == '*')

                    lookup[i][j] = lookup[i][j - 1] ||

                                   lookup[i - 1][j];

       

                // Текущие символы считаются

                // соответствие в двух случаях

                // (а) текущим символом шаблона является '?'

                // (б) символы действительно совпадают

                else if (pattern.charAt(j - 1) == '?' ||

                    str.charAt(i - 1) == pattern.charAt(j - 1))

                    lookup[i][j] = lookup[i - 1][j - 1];

       

                // Если символы не совпадают

                else lookup[i][j] = false;

            }

        }

       

        return lookup[n][m];

    }

       

    public static void main(String args[])

    {

        String str = "baaabab";

        String pattern = "*****ba*****ab";

        // String pattern = "ba ***** ab";

        // String pattern = "ba * ab";

        // String pattern = "a * ab";

        // String pattern = "a ***** ab";

        // String pattern = "* a ***** ab";

        // String pattern = "ba * ab ****";

        // String pattern = "****";

        // String pattern = "*";

        // String pattern = "aa? Ab";

        // String pattern = "b * b";

        // String pattern = "a * a";

        // String pattern = "baaabab";

        // String pattern = "? Baaabab";

        // String pattern = "* baaaba *";

       

        if (strmatch(str, pattern, str.length(),

                             pattern.length()))

            System.out.println("Yes");

        else

            System.out.println("No");

       

    }

}
// Этот код предоставлен Sumit Ghosh

C #

// C # программа для реализации подстановочного знака
// алгоритм сопоставления с образцом

using System;

  

class GFG

{     

      

    // Функция, которая соответствует входной строке с

    // данный шаблон

    static Boolean strmatch(String str,

                            String pattern, 

                            int n, int m)

    {

        // пустой шаблон может совпадать только с

        // пустая строка

        if (m == 0)

            return (n == 0);

      

        // таблица поиска для сохранения результатов

        // подзадачи

        Boolean[,] lookup = new Boolean[n + 1, 

                                        m + 1];

      

        // initailze таблица поиска в false

        for(int i = 0; i < n + 1; i++)

            for(int j = 0; j < m + 1; j++)

                lookup[i, j] = false;

          

        // пустой шаблон может соответствовать

        // пустая строка

        lookup[0, 0] = true;

      

        // Только '*' может совпадать с пустой строкой

        for (int j = 1; j <= m; j++)

            if (pattern[j - 1] == '*')

                lookup[0, j] = lookup[0, j - 1];

      

        // заполняем таблицу снизу вверх

        for (int i = 1; i <= n; i++)

        {

            for (int j = 1; j <= m; j++)

            {

                // Два случая, если мы видим '*'

                // а) Мы игнорируем символ * и перемещаемся

                // к следующему символу в шаблоне,

                // т.е. '*' указывает на пустую последовательность.

                // b) символ '*' совпадает с ith

                // символ на входе

                if (pattern[j - 1] == '*')

                    lookup[i, j] = lookup[i, j - 1] ||

                                   lookup[i - 1, j];

      

                // Текущие символы считаются

                // соответствие в двух случаях

                // (а) текущим символом шаблона является '?'

                // (б) символы действительно совпадают

                else if (pattern[j - 1] == '?' ||

                             str[i - 1] == pattern[j - 1])

                    lookup[i, j] = lookup[i - 1, j - 1];

      

                // Если символы не совпадают

                else lookup[i, j] = false;

            }

        }

        return lookup[n, m];

    }

      

    // Код драйвера

    public static void Main(String []args)

    {

        String str = "baaabab";

        String pattern = "*****ba*****ab";

        // String pattern = "ba ***** ab";

        // String pattern = "ba * ab";

        // String pattern = "a * ab";

        // String pattern = "a ***** ab";

        // String pattern = "* a ***** ab";

        // String pattern = "ba * ab ****";

        // String pattern = "****";

        // String pattern = "*";

        // String pattern = "aa? Ab";

        // String pattern = "b * b";

        // String pattern = "a * a";

        // String pattern = "baaabab";

        // String pattern = "? Baaabab";

        // String pattern = "* baaaba *";

      

        if (strmatch(str, pattern, str.Length,

                               pattern.Length))

            Console.WriteLine("Yes");

        else

            Console.WriteLine("No");

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход :

Yes

Временная сложность вышеуказанного решения составляет O (mxn). Используемое вспомогательное пространство также O (mxn).


Дальнейшие улучшения:

Мы можем улучшить сложность пространства, используя тот факт, что мы используем только результат из последней строки.
Еще одно улучшение — это слияние последовательных '*' в шаблоне с единичным '*', поскольку они означают одно и то же. Например, для шаблона «***** ba ***** ab», если мы объединяем последовательные звезды, результирующая строка будет «* ba * ab». Таким образом, значение m уменьшается с 14 до 6.

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Подстановочный шаблон

0.00 (0%) 0 votes