[openjudge] 와일드카드 문자열 일치 (dp)

3278 단어 문제풀이dp

제목 설명


전송문

문제풀이


이 문제가 처음에 나를 현혹시켰던 것은 하나의 *가 여러 글자와 일치할 수 있다는 것 같아서 이러면 할 수 없을 것 같아.사실 그렇게 생각할 필요 없어요.어디서 옮길지 생각만 하면 돼.f(i, j)는 첫 번째 열의 첫 번째 i 문자가 두 번째 열의 첫 번째 j 문자와 일치할 수 있는지를 나타낸다.그러면 분류 토론을 진행할 수 있다. ① 만약에 s1[i]='?또는 s1[i]=s2[j]이면 f(i, j)는 f(i-1, j-1)에서 옮길 수 있다.② s1[i]=∗이면 몇 가지 경우가 있다.가령 *가 하나의 문자를 대표한다고 가정하면 f(i-1, j-1)에서 똑같이 옮길 수 있다.빈 문자를 대표한다고 가정하면 f(i-1, j)에서 옮길 수 있다.만약 많은 문자를 대표한다고 가정하면 f(i, j-1)에서 옮길 수 있다.

코드

#include
#include
#include
using namespace std;

char s1[1005],s2[1005];
int l1,l2,f[1005][1005];

int main()
{
    gets(s1);l1=strlen(s1);
    gets(s2);l2=strlen(s2);
    for (int i=l1;i>=1;--i) s1[i]=s1[i-1];
    for (int i=l2;i>=1;--i) s2[i]=s2[i-1];
    for (int i=1;i<=l1;++i)
        if (s1[i]=='*') f[i][0]=true;
        else break;
    f[0][0]=true;
    for (int i=1;i<=l1;++i)
        for (int j=1;j<=l2;++j)
        {
            if (s1[i]=='?'||s1[i]==s2[j])
                f[i][j]|=f[i-1][j-1];
            else if (s1[i]=='*')
                f[i][j]|=f[i-1][i-1]|f[i-1][j]|f[i][j-1];
        }
    if (f[l1][l2]) puts("matched");
    else puts("not matched");
}
foreman을 시작할 때 읽는 프로파일에서 환경 변수를 설정합니다
상태 압축 dp

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage