Рубрики

Найти наименьшее окно в строке, содержащей все символы другой строки

Учитывая две строки string1 и string2, задача состоит в том, чтобы найти наименьшую подстроку в string1, эффективно содержащую все символы строки string2.

Примеры:

Input: string = “this is a test string”, pattern = “tist”
Output: Minimum window is “t stri”
Explanation: “t stri” contains all the characters of pattern.

Input: string = “geeksforgeeks”, pattern = “ork”
Output: Minimum window is “ksfor”

Метод 1 (решение грубой силы)
1- Генерация всех подстрок строки1 («это тестовая строка»)
2- Для каждой подстроки проверьте, содержит ли подстрока все символы строки2 («tist»)
3. Наконец, выведите наименьшую подстроку, содержащую все символы строки2.

Метод 2 (эффективное решение)

  1. Сначала проверьте, меньше ли длина строки, чем длина данного шаблона, если да, то « нет, такое окно не может существовать ».
  2. Сохраните вхождение символов данного шаблона в hash_pat [].
  3. Начните сопоставлять символы шаблона с символами строки, то есть счетчик приращений, если символ соответствует.
  4. Проверьте, если (количество == длина шаблона) это означает, что окно найдено.
  5. Если такое окно найдено, постарайтесь свести его к минимуму, удалив лишние символы из начала текущего окна.
  6. Обновите min_length.
  7. Распечатайте окно минимальной длины.

Схема для объяснения приведенного выше алгоритма:

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

C ++

// C ++ программа для поиска наименьшего окна, содержащего
// все символы шаблона.
#include<bits/stdc++.h>

using namespace std;

  

const int no_of_chars = 256;

  
// Функция для поиска наименьшего окна, содержащего
// все символы 'pat'
string findSubString(string str, string pat)
{

    int len1 = str.length();

    int len2 = pat.length();

  

    // проверяем, меньше ли длина строки, чем у шаблона

    // длина. Если да, то нет такого окна может существовать

    if (len1 < len2)

    {

        cout << "No such window exists";

        return "";

    }

  

    int hash_pat[no_of_chars] = {0};

    int hash_str[no_of_chars] = {0};

  

    // храним вхождения символов шаблона

    for (int i = 0; i < len2; i++)

        hash_pat[pat[i]]++;

  

    int start = 0, start_index = -1, min_len = INT_MAX;

  

    // начинаем обход строки

    int count = 0; // количество символов

    for (int j = 0; j < len1 ; j++)

    {

        // подсчитать вхождение символов строки

        hash_str[str[j]]++;

  

        // Если символ строки совпадает с символом шаблона

        // затем увеличиваем количество

        if (hash_pat[str[j]] != 0 &&

            hash_str[str[j]] <= hash_pat[str[j]] )

            count++;

  

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

        if (count == len2)

        {

            // Попробуем свернуть окно, т. Е. Проверить,

            // любой символ встречается больше нет. времен

            // чем его вхождение в шаблон, если да

            // затем удаляем его из запуска, а также удаляем

            // бесполезные символы.

            while ( hash_str[str[start]] > hash_pat[str[start]]

                || hash_pat[str[start]] == 0)

            {

  

                if (hash_str[str[start]] > hash_pat[str[start]])

                    hash_str[str[start]]--;

                start++;

            }

  

            // обновляем размер окна

            int len_window = j - start + 1;

            if (min_len > len_window)

            {

                min_len = len_window;

                start_index = start;

            }

        }

    }

  

    // Если окно не найдено

    if (start_index == -1)

    {

    cout << "No such window exists";

    return "";

    }

  

    // Возвращаем подстроку начиная с start_index

    // и длина min_len

    return str.substr(start_index, min_len);

}

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

int main()

{

    string str = "this is a test string";

    string pat = "tist";

  

    cout << "Smallest window is : \n"

        << findSubString(str, pat);

    return 0;

}

Джава

// Java-программа для поиска наименьшего окна, содержащего
// все символы шаблона.

  

public class GFG 

{

    static final int no_of_chars = 256;

      

    // Функция для поиска наименьшего окна, содержащего

    // все символы 'pat'

    static String findSubString(String str, String pat)

    {

        int len1 = str.length();

        int len2 = pat.length();

      

        // проверяем, меньше ли длина строки, чем у шаблона

        // длина. Если да, то нет такого окна может существовать

        if (len1 < len2)

        {

            System.out.println("No such window exists");

            return "";

        }

      

        int hash_pat[] = new int[no_of_chars];

        int hash_str[] = new int[no_of_chars];

      

        // храним вхождения символов шаблона

        for (int i = 0; i < len2; i++)

            hash_pat[pat.charAt(i)]++;

      

        int start = 0, start_index = -1, min_len = Integer.MAX_VALUE;

      

        // начинаем обход строки

        int count = 0; // количество символов

        for (int j = 0; j < len1 ; j++)

        {

            // подсчитать вхождение символов строки

            hash_str[str.charAt(j)]++;

      

            // Если символ строки совпадает с символом шаблона

            // затем увеличиваем количество

            if (hash_pat[str.charAt(j)] != 0 &&

                hash_str[str.charAt(j)] <= hash_pat[str.charAt(j)] )

                count++;

      

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

            if (count == len2)

            {

                // Попробуем свернуть окно, т. Е. Проверить,

                // любой символ встречается больше нет. времен

                // чем его вхождение в шаблон, если да

                // затем удаляем его из запуска, а также удаляем

                // бесполезные символы.

                while ( hash_str[str.charAt(start)] > hash_pat[str.charAt(start)]

                    || hash_pat[str.charAt(start)] == 0)

                {

      

                    if (hash_str[str.charAt(start)] > hash_pat[str.charAt(start)])

                        hash_str[str.charAt(start)]--;

                    start++;

                }

      

                // обновляем размер окна

                int len_window = j - start + 1;

                if (min_len > len_window)

                {

                    min_len = len_window;

                    start_index = start;

                }

            }

        }

      

        // Если окно не найдено

        if (start_index == -1)

        {

        System.out.println("No such window exists");

        return "";

        }

      

        // Возвращаем подстроку начиная с start_index

        // и длина min_len

        return str.substring(start_index, start_index + min_len);

    }

      

    // Метод драйвера

    public static void main(String[] args)

    {

        String str = "this is a test string";

        String pat = "tist";

      

    System.out.print("Smallest window is :\n " +

                        findSubString(str, pat));

    }

}

python3

# Python3 программа для поиска самого маленького окна
# содержит все символы шаблона.

no_of_chars = 256

  
# Функция найти самое маленькое окно
# содержит все символы 'pat'

def findSubString(string, pat): 

  

    len1 = len(string) 

    len2 = len(pat) 

  

    # проверить, если длина строки меньше, чем шаблон

    # длина Если да, то нет такого окна может существовать

    if len1 < len2: 

      

        print("No such window exists"

        return "" 

  

    hash_pat = [0] * no_of_chars

    hash_str = [0] * no_of_chars 

  

    # хранить вхождения символов шаблона

    for i in range(0, len2): 

        hash_pat[ord(pat[i])] += 1

  

    start, start_index, min_len = 0, -1, float('inf'

  

    # начать обход строки

    count = 0 # количество символов

    for j in range(0, len1): 

      

        # считать вхождение символов строки

        hash_str[ord(string[j])] += 1

  

        # Если символ строки соответствует

        символ # шаблона затем увеличивает число

        if (hash_pat[ord(string[j])] != 0 and

            hash_str[ord(string[j])] <= 

            hash_pat[ord(string[j])]): 

            count += 1

  

        # если все символы совпадают

        if count == len2: 

          

            # Попробуйте свернуть окно, т. Е. Проверить,

            # любой персонаж происходит больше нет. времен

            # чем его вхождение в шаблон, если да

            # затем удалите его из запуска, а также удалите

            # бесполезные персонажи.

            while (hash_str[ord(string[start])] > 

                   hash_pat[ord(string[start])] or

                   hash_pat[ord(string[start])] == 0): 

              

                if (hash_str[ord(string[start])] > 

                    hash_pat[ord(string[start])]): 

                    hash_str[ord(string[start])] -= 1

                start += 1

              

            # обновить размер окна

            len_window = j - start + 1

            if min_len > len_window: 

              

                min_len = len_window 

                start_index = start 

  

    # Если окно не найдено

    if start_index == -1:

        print("No such window exists"

        return "" 

      

    # Возвращаем подстроку, начиная с

    # start_index и длина min_len

    return string[start_index : start_index + min_len] 

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

if __name__ == "__main__":

  

    string = "this is a test string"

    pat = "tist"

  

    print("Smallest window is : ")

    print(findSubString(string, pat)) 

      
# Этот код предоставлен Rituraj Jain

C #

// C # программа для поиска наименьшего окна, содержащего
// все символы шаблона.

using System;

  

class GFG 

{

    static int no_of_chars = 256;

      

    // Функция для поиска наименьшего окна, содержащего

    // все символы 'pat'

    static String findSubString(String str, String pat)

    {

        int len1 = str.Length;

        int len2 = pat.Length;

      

        // проверяем, меньше ли длина строки, чем у шаблона

        // длина. Если да, то нет такого окна может существовать

        if (len1 < len2)

        {

            Console.WriteLine("No such window exists");

            return "";

        }

      

        int []hash_pat = new int[no_of_chars];

        int []hash_str = new int[no_of_chars];

      

        // храним вхождения символов шаблона

        for (int i = 0; i < len2; i++)

            hash_pat[pat[i]]++;

      

        int start = 0, start_index = -1, min_len = int.MaxValue;

      

        // начинаем обход строки

        int count = 0; // количество символов

        for (int j = 0; j < len1 ; j++)

        {

            // подсчитать вхождение символов строки

            hash_str[str[j]]++;

      

            // Если символ строки совпадает с символом шаблона

            // затем увеличиваем количество

            if (hash_pat[str[j]] != 0 &&

                hash_str[str[j]] <= hash_pat[str[j]] )

                count++;

      

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

            if (count == len2)

            {

                // Попробуем свернуть окно, т. Е. Проверить,

                // любой символ встречается больше нет. времен

                // чем его вхождение в шаблон, если да

                // затем удаляем его из запуска, а также удаляем

                // бесполезные символы.

                while ( hash_str[str[start]] > hash_pat[str[start]]

                    || hash_pat[str[start]] == 0)

                {

      

                    if (hash_str[str[start]] > hash_pat[str[start]])

                        hash_str[str[start]]--;

                    start++;

                }

      

                // обновляем размер окна

                int len_window = j - start + 1;

                if (min_len > len_window)

                {

                    min_len = len_window;

                    start_index = start;

                }

            }

        }

      

        // Если окно не найдено

        if (start_index == -1)

        {

            Console.WriteLine("No such window exists");

            return "";

        }

      

        // Возвращаем подстроку начиная с start_index

        // и длина min_len

        return str.Substring(start_index, min_len);

    }

      

    // Метод драйвера

    public static void Main(String[] args)

    {

        String str = "this is a test string";

        String pat = "tist";

      

        Console.WriteLine("Smallest window is :\n " +

                        findSubString(str, pat));

    }

}

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

PHP

<?php
// PHP программа для поиска наименьшего окна
// содержащий все символы шаблона.

  

define("no_of_chars", 256); 

  
// Функция для поиска наименьшего окна
// содержащий все символы 'pat'

function findSubString(&$str, &$pat

    $len1 = strlen($str); 

    $len2 = strlen($pat); 

  

    // проверяем, меньше ли длина строки

    // чем длина шаблона. Если да

    // тогда такого окна не может быть

    if ($len1 < $len2

    

        echo "No such window exists"

        return ""

    

  

    $hash_pat = array_fill(0, no_of_chars, 0); 

    $hash_str = array_fill(0, no_of_chars, 0); 

  

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

    // шаблона

    for ($i = 0; $i < $len2; $i++) 

        $hash_pat[ord($pat[$i])]++; 

  

    $start = 0;

    $start_index = -1;

    $min_len = PHP_INT_MAX; 

  

    // начинаем обход строки

    $count = 0; // количество символов

    for ($j = 0; $j < $len1 ; $j++) 

    

        // подсчитать вхождение символов

        // строки

        $hash_str[ord($str[$j])]++; 

  

        // Если символ строки соответствует

        // символ шаблона затем увеличить счетчик

        if ($hash_pat[ord($str[$j])] != 0 && 

            $hash_str[ord($str[$j])] <=

            $hash_pat[ord($str[$j])]) 

            $count++; 

  

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

        if ($count == $len2

        

            // Попробуем свернуть окно, т.е.

            // проверяем, встречается ли какой-либо символ

            // больше нет раз, чем его возникновение

            // в шаблоне, если да, то удалить его из

            // запуск, а также удаление ненужного

            // персонажи.

            while ($hash_str[ord($str[$start])] > 

                   $hash_pat[ord($str[$start])] || 

                   $hash_pat[ord($str[$start])] == 0) 

            

  

                if ($hash_str[ord($str[$start])] >

                    $hash_pat[ord($str[$start])]) 

                    $hash_str[ord($str[$start])]--; 

                $start++; 

            

  

            // обновляем размер окна

            $len_window = $j - $start + 1; 

            if ($min_len > $len_window

            

                $min_len = $len_window

                $start_index = $start

            

        

    

  

    // Если окно не найдено

    if ($start_index == -1) 

    

        echo "No such window exists"

        return ""

    

  

    // Возвращаем подстроку начиная с

    // start_index и длина min_len

    return substr($str, $start_index, $min_len); 

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

$str = "this is a test string"

$pat = "tist"

  

echo "Smallest window is : \n" .

      findSubString($str, $pat); 

        
// Этот код предоставлен
// ратбхупендра
?>


Выход:

Smallest window is : 
t stri

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

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

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

Найти наименьшее окно в строке, содержащей все символы другой строки

0.00 (0%) 0 votes