[골5] 16500 - 문자열 판별

#include <iostream>
#include <string>

using namespace std;

#pragma region 입출력 속도향상

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

#pragma endregion

int main()
{
	string a[100];
	string s;
	int dp[101];
	int n;

	cin >> s >> n;
	
	for (int i = 0; i < n; i++)
		cin >> a[i];

	int sl = s.length();

	dp[sl] = 1;

	for (int i = sl - 1; i >= 0; i--)
	{
		for (int j = 0; j <= n; j++)
		{
			if (s.find(a[j], i) == i &&
				dp[i + a[j].length()] == 1)
			{
				dp[i] = 1;
				break;
			}
			else
				dp[i] = 0;
		}
	}
	cout << dp[0];
	return 0;
}