Wildcard(Wildcard)

https://algospot.com/judge/problem/read/WILDCARD#c7900

이 코드들은 외울정도로 다시 풀어봐야겠다.

2개의 코드를 올리겠다.

1. 시간 복잡도 n^3

2. 시간 복잡도 n^2

첫 번째 코드의 40번 째 줄 skip + s <= S.size()에서 '<'가 아님을 주의하자.

반례) *p*, help

시간 복잡도 n^3

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
string W, S;
 
int cache[102][102] = { 0, };
 
// 와일드카드 패턴 W[w...]가 문자열 S[s...]에 대응되는지 여부를 반환한다.
int matchMemoized(int w, int s)
{
    // 메모이제이션
    int & ret = cache[w][s];
 
    if (ret != -1) return ret;
 
    // W[w]와 S[s]를 맞춰나간다.
    while (s < S.size() && w < W.size() && (W[w] == '?' || W[w] == S[s]))
    {
        ++w; ++s;
    }
 
    // 더이상 대응할 수 없으면 왜 while문이 끝났는지 확인한다.
 
    // 2. 패턴 끝에 도달해서 끝난 경우 : 문자열도 끝났어야 참.
    if (w == W.size()) return ret = (s == S.size());
 
    // 4. *를 만나서 끝난 경우 : *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다.
    if (W[w] == '*')
    {
        for (int skip = 0; skip + s <= S.size(); ++skip)
        {
            if (matchMemoized(w + 1, s + skip)) return ret = 1;
        }
    }
 
    // 3. 이 외의 경우에는 모두 대응되지 않는다.
    return ret = 0;
}
 
int main(void)
{
    int N = 0, T = 0;
 
    vector<string> v;
 
    scanf("%d", &T);
 
    while (T--)
    {
        v.clear();
 
        cin >> W; // 와일드 카드 문자열
 
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++)
        {
            fill(&cache[0][0], &cache[101][102], -1);
 
            cin >> S; // 문자열 입력
 
            if (matchMemoized(0, 0) == 1) v.push_back(S);
        }
 
        sort(v.begin(), v.end());
 
        for (auto i : v) cout << i << '\n';
    }
 
    return 0;
}

시간 복잡도 n^2

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
string W, S;
 
int cache[102][102] = { 0, };
 
// 와일드카드 패턴 W[w...]가 문자열 S[s...]에 대응되는지 여부를 반환한다.
int matchMemoized(int w, int s)
{
    // 메모이제이션
    int & ret = cache[w][s];
 
    if (ret != -1) return ret;
 
    // w와 s를 1씩 증가하고 계속하는 대신에 패턴과 문자열의 첫 한 글자씩을 뗴고 이들이 서로 대응되는지 재귀호출로 확인
    if (s < S.size() && w < W.size() && (W[w] == '?' || W[w] == S[s])) return ret = matchMemoized(w + 1, s + 1);
 
    // 2. 패턴 끝에 도달해서 끝난 경우 : 문자열도 끝났어야 참.
    if (w == W.size()) return ret = (s == S.size());
 
    // 4. *를 만나서 끝난 경우 : *에 아무 글자도 대응시키지 않을 것인지, 아니면 한 글자를 더 대응시킬 것인지
    if (W[w] == '*')
    {
        if (matchMemoized(w + 1, s) || (s < S.size() && matchMemoized(w, s + 1))) return ret = 1;
    }
 
    // 3. 이 외의 경우에는 모두 대응되지 않는다.
    return ret = 0;
}
 
int main(void)
{
    int N = 0, T = 0;
 
    vector<string> v;
 
    scanf("%d", &T);
 
    while (T--)
    {
        v.clear();
 
        cin >> W; // 와일드 카드 문자열
 
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++)
        {
            fill(&cache[0][0], &cache[101][102], -1);
 
            cin >> S; // 문자열 입력
 
            if (matchMemoized(0, 0) == 1) v.push_back(S);
        }
 
        sort(v.begin(), v.end());
 
        for (auto i : v) cout << i << '\n';
    }
 
    return 0;
}