백준 - 1593번 : 문자 해독 (C++)

풀이 방법 : 슬라이딩 윈도우

W 문자열에 들어있는 문자가 S에 순서에 상관없이 들어 있으면 그 단어가 될 수 있다.
cAda가 들어있는지 확인하려면 dAac, Acad, cadA 등 문자의 순서와 상관없이 갯수만 일치하면 된다는 것이다.

슬라이딩 윈도우를 통해 대문자와 소문자 둘 다 고려하면서 부분 문자열에 포함된 문자의 갯수를 카운팅해서 W의 갯수와 일치하면 경우의 수를 증가시켜 주면 된다.

#include <iostream>

using namespace std;

int WCnt[128] = {};
int CurCnt[128] = { };

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int g, s;
	cin >> g >> s;

	string W, S;
	cin >> W >> S;

	for (int i = 0; i < g; ++i)
	{
		++WCnt[(int)W[i]];
		++CurCnt[(int)S[i]];
	}

	int Cnt = 0;

	for (int i = 0; i <= s - g; ++i)
	{
		bool Enable = true;
		for (int j = 0; j < g; ++j)
		{
			if (WCnt[(int)W[j]] != CurCnt[(int)W[j]])
			{
				Enable = false;
				break;
			}
		}

		if (Enable)
			++Cnt;

		--CurCnt[(int)S[i]];

		if(i + g <= s)
			++CurCnt[(int)S[i + g]];
	}

	cout << Cnt;

}