wildCard알고리즘에서 캐시배열이 언제 쓰이는지 모르겠어요 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찍고 디버그를 아무리 돌려도 걸리는 문자(?)가 없네요 대체 캐시배열은 어떤 문자들을 입력했을때 쓰이는 건지 궁금합니다! 8년 전
1개의 댓글이 있습니다. JongMan ret != -1 입니다. 캐시 배열은 match2() 함수에 같은 입력이 두 번 주어질 때 사용됩니다. ***a 와 aaab에 대해 수행해 보세요. 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
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찍고 디버그를 아무리 돌려도 걸리는 문자(?)가 없네요
대체 캐시배열은 어떤 문자들을 입력했을때 쓰이는 건지 궁금합니다!
8년 전