백준 5015번 ls

문제 링크입니다: https://www.acmicpc.net/problem/5015

Algospot Wildcard(https://jaimemin.tistory.com/315)와 동일한 문제였습니다.

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 100 + 1;

 

int N;

string P, S;

int cache[MAX][MAX];

 

int func(int pIdx, int sIdx)

{

        int &result = cache[pIdx][sIdx];

        if (result != -1)

                 return result;

 

        //둘이 일치하면

        if (pIdx < P.size() && sIdx < S.size() && P[pIdx] == S[sIdx])

                 return result = func(pIdx + 1, sIdx + 1);

 

        //패턴 끝에 도달했고 문자열도 끝에 도달했다

        if (pIdx == P.size() && sIdx == S.size())

                 return result = 1;

 

        //*가 몇 글자를 대응해야 하는지 재귀호출을 통해 확인

        if (P[pIdx] == '*')

                 if (func(pIdx + 1, sIdx) || (pIdx < P.size() && func(pIdx, sIdx + 1)))

                         return result = 1;

 

        return result = 0;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> P;

 

        cin >> N;

        vector<string> result;

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

        {

                 cin >> S;

 

                 memset(cache, -1, sizeof(cache));

                 if (func(0, 0))

                         result.push_back(S);

        }

 

        for (int i = 0; i < result.size(); i++)

                 cout << result[i] << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~