16500번 문자열 판별

문제 링크

문자열 판별

문제 풀이

현재 볼 문자열의 위치에서 똑같은 문자열이 존재하면 그 문자열의 길이만큼 index를 더한후 재귀 호출한다. index가 볼 문자열의 끝에 도착할 때를 기저 사례로 하고 1을 리턴한다.

구현

#include <iostream> 
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

string S, A[101];
int N;
int cache[101];

int solve(int index) {
    if (index == S.size()) return 1;

    int& ret = cache[index];
    if (ret != -1) return ret;
    
    ret = 0;
    for (int i = 0; i < N; ++i) {
        int flag = 1;
        for (int j = 0; j < A[i].size(); ++j)
            if (S[index + j] != A[i][j]) 
                flag = 0;
        if (flag)
            ret |= solve(index + A[i].size());
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> S >> N;
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    memset(cache, -1, sizeof(cache));

    cout << solve(0);
    return 0;
}