Kohila G Ответов: 2

Элемент массива внутри квадратной скобки другого массива


Найдите самое маленькое окно в строке, содержащей все символы другой строки - GeeksforGeeks[^]

Я не могу разобраться в этом коде. Что означает массив внутри массива? Как символ может быть индексом массива?

Что я уже пробовал:

// C++ program to find smallest window containing 
// all characters of a pattern. 
#include<bits/stdc++.h> 
using namespace std; 

const int no_of_chars = 256; 

// Function to find smallest window containing 
// all characters of 'pat' 
string findSubString(string str, string pat) 
{ 
	int len1 = str.length(); 
	int len2 = pat.length(); 

	// check if string's length is less than pattern's 
	// length. If yes then no such window can exist 
	if (len1 < len2) 
	{ 
		cout << "No such window exists"; 
		return ""; 
	} 

	int hash_pat[no_of_chars] = {0}; 
	int hash_str[no_of_chars] = {0}; 

	// store occurrence ofs characters of pattern 
	for (int i = 0; i < len2; i++) 
		hash_pat[pat[i]]++; 

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

	// start traversing the string 
	int count = 0; // count of characters 
	for (int j = 0; j < len1 ; j++) 
	{ 
		// count occurrence of characters of string 
		hash_str[str[j]]++; 

		// If string's char matches with pattern's char 
		// then increment count 
		if (hash_pat[str[j]] != 0 && 
			hash_str[str[j]] <= hash_pat[str[j]] ) 
			count++; 

		// if all the characters are matched 
		if (count == len2) 
		{ 
			// Try to minimize the window i.e., check if 
			// any character is occurring more no. of times 
			// than its occurrence in pattern, if yes 
			// then remove it from starting and also remove 
			// the useless characters. 
			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++; 
			} 

			// update window size 
			int len_window = j - start + 1; 
			if (min_len > len_window) 
			{ 
				min_len = len_window; 
				start_index = start; 
			} 
		} 
	} 

	// If no window found 
	if (start_index == -1) 
	{ 
	cout << "No such window exists"; 
	return ""; 
	} 

	// Return substring starting from start_index 
	// and length min_len 
	return str.substr(start_index, min_len); 
} 

// Driver code 
int main() 
{ 
	string str = "this is a test string"; 
	string pat = "tist"; 

	cout << "Smallest window is : \n"
		<< findSubString(str, pat); 
	return 0; 
} 

2 Ответов

Рейтинг:
19

Rick York

Вы должны думать о том, какие данные предоставляет каждый слой. Переменная str, строка, представляет собой массив символов. Символ - это просто целое число в один байт. Это означает, что значение str[j] - это целое число, которое может находиться в диапазоне от 0 до 255, то есть в диапазоне одного байта. Это значение используется для индексации массивов hash_pat и hash_str длиной 256 элементов.

Это может быть более ясно для вас, если вы расширите выражение следующим образом :

for( int i = 0; i < len2; ++i )
{
    int index = pat[i];
    ++hash_pat[index];
}
Это просто берет внутреннее выражение и сохраняет его во временной переменной под названием index, но в этом случае происходит то же самое.

FWIW, если бы это был мой код, я бы гораздо больше использовал временные переменные. Во - первых, я думаю, что это облегчает просмотр вещей в отладчике. Вот вам пример :
for (int j = 0; j < len1 ; j++)
{
    int tempstrj = str[j];
    // count occurrence of characters of string
    hash_str[tempstrj]++;

    // If string's char matches with pattern's char
    // then increment count
    if (hash_pat[tempstrj] != 0 &&
        hash_str[tempstrj] <= hash_pat[tempstrj] )
        count++;

    // if all the characters are matched
    if (count == len2)
    {
        // Try to minimize the window i.e., check if
        // any character is occurring more no. of times
        // than its occurrence in pattern, if yes
        // then remove it from starting and also remove
        // the useless characters.
        int tempstrst = str[start];
        while ( hash_str[tempstrst] > hash_pat[tempstrst]
            || hash_pat[tempstrst] == 0)
        {

            if (hash_str[tempstrst] > hash_pat[tempstrst])
                hash_str[tempstrst]--;
            start++;
        }

        // update window size
        int len_window = j - start + 1;
        if (min_len > len_window)
        {
            min_len = len_window;
            start_index = start;
        }
    }
}


Nelek

Хорошее объяснение +5.

Rick York

Спасибо.

Kohila G

четкое разъяснение. Большое спасибо.

Рейтинг:
10

Patrice T

Цитата:
Как символ может быть индексом массива?

Узнайте больше о кодировании ASCII.

Вы не понимаете, что делает этот код, вам может помочь инструмент, это отладчик !

Запускайте свой код на отладчике шаг за шагом, проверяйте переменные.
Отладчик здесь, чтобы показать вам, что делает ваш код, и ваша задача-сравнить с тем, что он должен делать.
В отладчике нет никакой магии, он не знает, что должен делать ваш код, он не находит ошибок, он просто помогает вам, показывая, что происходит. Когда код не делает того, что ожидается, вы близки к ошибке.
Чтобы увидеть, что делает ваш код: просто установите точку останова и посмотрите, как работает ваш код, отладчик позволит вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения.

Отладчик - Википедия, свободная энциклопедия[^]

Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]
Базовая отладка с помощью Visual Studio 2010 - YouTube[^]

1.11 — отладка программы (пошаговое выполнение и останова) | выучить C++[^]

Отладчик здесь только для того, чтобы показать вам, что делает ваш код, и ваша задача-сравнить его с тем, что он должен делать.


Kohila G

Это так полезно. Огромное спасибо.