Рубрики

Соответствие строки, где одна строка содержит символы подстановки

Даны две строки, где первая строка может содержать символы подстановки, а вторая строка — обычная строка. Напишите функцию, которая возвращает true, если две строки совпадают. Следующие разрешенные символы подстановки в первой строке.

* --> Matches with 0 or more instances of any character or set of characters.
? --> Matches with any one character.

Например, «g * ks» совпадает с «geeks». И строка «ge? Ks *» совпадает с «geeksforgeeks» (обратите внимание на '*' в конце первой строки). Но «g * k» не совпадает с «gee», так как символ «k» отсутствует во второй строке.

C ++

// AC программа для подстановки подстановочных знаков
#include <stdio.h>
#include <stdbool.h>

  
// Основная функция, которая проверяет наличие двух заданных строк
// совпадение. Первая строка может содержать символы подстановки

bool match(char *first, char * second)

{

    // Если мы достигаем в конце обеих строк, мы сделали

    if (*first == '\0' && *second == '\0')

        return true;

  

    // Убедитесь, что символы после '*' присутствуют

    // во второй строке. Эта функция предполагает, что первый

    // строка не будет содержать два последовательных символа '*'

    if (*first == '*' && *(first+1) != '\0' && *second == '\0')

        return false;

  

    // Если первая строка содержит '?' Или текущие символы

    // обе строки совпадают

    if (*first == '?' || *first == *second)

        return match(first+1, second+1);

  

    // Если есть *, то есть две возможности

    // а) Рассмотрим текущий символ второй строки

    // б) Мы игнорируем текущий символ второй строки.

    if (*first == '*')

        return match(first+1, second) || match(first, second+1);

    return false;

}

  
// Функция для запуска тестовых случаев

void test(char *first, char *second)

{  match(first, second)? puts("Yes"): puts("No"); }

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    test("g*ks", "geeks"); // Да

    test("ge?ks*", "geeksforgeeks"); // Да

    test("g*k", "gee");  // Нет, потому что 'k' не во втором

    test("*pqrs", "pqrst"); // Нет, потому что 't' не в первом

    test("abc*bcd", "abcdhghgbcd"); // Да

    test("abc*c?d", "abcd"); // Нет, потому что второй должен иметь 2

                             // экземпляры 'c'

    test("*c*d", "abcd"); // Да

    test("*?c*d", "abcd"); // Да

    return 0;

}

Джава

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

class GFG 

{

  
// Основная функция, которая проверяет,
// две заданные строки совпадают. Первая строка
// может содержать символы подстановки

static boolean match(String first, String second) 

{

  

    // Если мы достигаем в конце обеих строк,

    // мы сделали

    if (first.length() == 0 && second.length() == 0)

        return true;

  

    // Убедитесь, что символы после '*'

    // присутствуют во второй строке.

    // Эта функция предполагает, что первый

    // строка не будет содержать два последовательных символа '*'

    if (first.length() > 1 && first.charAt(0) == '*' && 

                              second.length() == 0)

        return false;

  

    // Если первая строка содержит «?»,

    // или текущие символы обеих строк совпадают

    if ((first.length() > 1 && first.charAt(0) == '?') || 

        (first.length() != 0 && second.length() != 0 && 

         first.charAt(0) == second.charAt(0)))

        return match(first.substring(1), 

                     second.substring(1));

  

    // Если есть *, то есть две возможности

    // а) Рассмотрим текущий символ второй строки

    // б) Мы игнорируем текущий символ второй строки.

    if (first.length() > 0 && first.charAt(0) == '*')

        return match(first.substring(1), second) || 

               match(first, second.substring(1));

    return false;

}

  
// Функция для запуска тестовых случаев

static void test(String first, String second)

{

    if (match(first, second))

        System.out.println("Yes");

    else

        System.out.println("No");

}

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

public static void main(String[] args) 

{

    test("g*ks", "geeks"); // Да

    test("ge?ks*", "geeksforgeeks"); // Да

    test("g*k", "gee"); // Нет, потому что 'k' не во втором

    test("*pqrs", "pqrst"); // Нет, потому что 't' не в первом

    test("abc*bcd", "abcdhghgbcd"); // Да

    test("abc*c?d", "abcd"); // Нет, потому что второй должен иметь 2

                            // экземпляры 'c'

    test("*c*d", "abcd"); // Да

    test("*?c*d", "abcd"); // Да

}
}

  
// Этот код предоставлен
// sanjeev2552

питон

# Python программа для подстановки символов подстановки

  
# Основная функция, которая проверяет, совпадают ли две заданные строки.
# Первая строка может содержать символы подстановки

def match(first, second):

  

    # Если мы достигаем в конце обеих строк, мы сделали

    if len(first) == 0 and len(second) == 0:

        return True

  

    # Убедитесь, что присутствуют символы после '*'

    # во второй строке. Эта функция предполагает, что первый

    # строка не будет содержать два последовательных символа '*'

    if len(first) > 1 and first[0] == '*' and  len(second) == 0:

        return False

  

    # Если первая строка содержит «?» Или текущие символы

    количество строк совпадает

    if (len(first) > 1 and first[0] == '?') or (len(first) != 0

        and len(second) !=0 and first[0] == second[0]):

        return match(first[1:],second[1:]);

  

    # Если есть *, то есть две возможности

    # a) Мы рассматриваем текущий символ второй строки

    # б) Мы игнорируем текущий символ второй строки.

    if len(first) !=0 and first[0] == '*':

        return match(first[1:],second) or match(first,second[1:])

  

    return False

  
# Функция для запуска тестовых случаев

def test(first, second):

    if match(first, second):

        print "Yes"

    else:

        print "No"

  
# Драйверная программа

test("g*ks", "geeks") # Да

test("ge?ks*", "geeksforgeeks") # Да

test("g*k", "gee") # Нет, потому что «к» не во втором

test("*pqrs", "pqrst") # Нет, потому что 't' не в первом

test("abc*bcd", "abcdhghgbcd") # Да

test("abc*c?d", "abcd") # Нет, потому что секунда должна иметь 2 экземпляра 'c'

test("*c*d", "abcd") # Да

test("*?c*d", "abcd") # Да

  
# Этот код предоставлен BHAVYA JAIN и ROHIT SIKKA


Выход:

Yes
Yes
No
No
Yes
No
Yes
Yes

Упражнение
1) В приведенном выше решении все не подстановочные символы первой строки должны содержать вторую строку, а все символы второй строки должны совпадать либо с нормальным символом, либо с подстановочным знаком первой строки. Расширьте вышеприведенное решение, чтобы оно работало как другие решения для поиска по шаблону, где первая строка — это шаблон, а вторая строка — это текст, и мы должны печатать все вхождения первой строки за секунду.

2) Напишите функцию поиска по шаблону, где значение «?» то же самое, но «*» означает 0 или более вхождений символа непосредственно перед «*». Например, если первая строка 'a * b', то она совпадает с 'aaab', но не совпадает с 'abb'.

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

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

Соответствие строки, где одна строка содержит символы подстановки

0.00 (0%) 0 votes