wildCard알고리즘에서 캐시배열이 언제 쓰이는지 모르겠어요

  • wddtev
    wddtev

    알고리즘 문제해결전략의 소스를 인용하자면

    string W,S;
    int cache[101][101];
    bool match2(int w,int s)
    {
    int &ret = cache[w][s];
    if(ret == -1)
    return ret; // ★★Break Point★★
    while(s<S.size() && w<W.size() && (W[w] =='?' || W[w] == S[s]))
    {
    ++w;
    ++s;
    }
    if(w==W.size())
    return ret=(s==S.size());
    if(W[w] == '*')
    for(int i=0;i+s<=S.size();i++)
    if(match2(w+1,s+i))
    return ret = 1;
    return ret=0;

    }

    9번째줄 return ret 에 Break Point찍고 디버그를 아무리 돌려도 걸리는 문자(?)가 없네요
    대체 캐시배열은 어떤 문자들을 입력했을때 쓰이는 건지 궁금합니다!


    2년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan
    1. ret != -1 입니다.
    2. 캐시 배열은 match2() 함수에 같은 입력이 두 번 주어질 때 사용됩니다. ***aaaab에 대해 수행해 보세요.

    2년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.