dp를 사용하여 커플 링

Question

두 개의 문자열 S1 & S2가 주어졌습니다. 득점 페널티, 불일치 점수 및 경기 점수가 주어진 점수 체계.

S2와 가장 일치하는 S1을 찾으십시오.

제 아이디어는 가능한 모든 S1을 나열한 다음 하나씩 S2와 매치하는 것입니다. brute force를 사용하여 가능한 모든 S1을 나열하십시오. 그런 다음 dp를 사용하여 가능한 S1을 S2와 일치시킵니다.

빠른 방법이 있습니까? 또는 어떤 참조를 제안합니까? 하나 이런 식으로 뭔가를 코딩 할 수 위키 백과와 생각을 조금 사용

Answer 1

:

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

#ifndef MAX 
#define MAX(a,b) ((a)>(b)?(a):(b)) 
#endif 

#define MATCH_SCORE  2 
#define MISMATCH_SCORE -1 
#define GAP_SCORE  0 

// Calculates the match score recursively. 
long MatchScore(const char* p/* in: may contain 'x' */, 
       const char* s/* in: doesn't contain 'x' */) 
{ 
    long res; 

    if (*p && *s) 
    { 
    if ((*p == *s) || 
     ((*p == 'x') && (*s >= 'a') && (*s <= 'f'))) 
    { 
     res = MatchScore(p + 1, s + 1) + MATCH_SCORE; 
    } 
    else 
    { 
     long s1 = MatchScore(p + 1, s + 1) + MISMATCH_SCORE; 
     long s2 = MatchScore(p, s + 1) + GAP_SCORE; 
     long s3 = MatchScore(p + 1, s) + GAP_SCORE; 
     res = MAX(s1, MAX(s2, s3)); 
    } 
    } 
    else 
    { 
    res = GAP_SCORE * (long)(strlen(p) + strlen(s)); 
    } 

    return res; 
} 

// Calculates the best matching string and the match score 
// using dynamic programming, the score must be the same 
// as returned by MatchScore(). 
void FindBestMatch(const char* p/* in: may contain 'x' */, 
        const char* s/* in: doesn't contain 'x' */, 
        long* score/* out: match score */, 
        char** match/* out: best matching string */) 
{ 
    size_t lp = strlen(p) + 1; 
    size_t ls = strlen(s) + 1; 
    size_t i, j; 
    long* table = (long*)malloc(lp * ls * sizeof(long)); 

    for (i = 0; i < lp; i++) 
    table[0 * lp + i] = GAP_SCORE * i; 

    for (j = 0; j < ls; j++) 
    table[j * lp + 0] = GAP_SCORE * j; 

    for (j = 1; j < ls; j++) 
    { 
    for (i = 1; i < lp; i++) 
    { 
     if ((p[i-1] == s[j-1]) || 
      ((p[i-1] == 'x') && (s[j-1] >= 'a') && (s[j-1] <= 'f'))) 
     { 
     table[j * lp + i] = table[(j-1) * lp + (i-1)] + MATCH_SCORE; 
     } 
     else 
     { 
     table[j * lp + i] = 
      MAX(table[(j-1) * lp + (i-1)] + MISMATCH_SCORE, 
       MAX(table[(j-1) * lp + i] + GAP_SCORE, 
        table[j * lp + (i-1)] + GAP_SCORE)); 
     } 
    } 
    } 

    *score = table[lp * ls - 1]; 

    // Now, trace back the score table and construct the best matching string 

    *match = (char*)malloc(lp); 
    (*match)[lp - 1] = '\0'; 

    for (j = ls, i = lp; j || i;) 
    { 
    if ((p[i-1] == s[j-1]) || 
     ((p[i-1] == 'x') && (s[j-1] >= 'a') && (s[j-1] <= 'f'))) 
    { 
     (*match)[i-1] = s[j-1]; 
     j--; 
     i--; 
    } 
    else 
    { 
     if (table[(j-1) * lp + i] > table[j * lp + (i-1)]) 
     { 
     j--; 
     } 
     else 
     { 
     (*match)[i-1] = p[i-1]; 
     i--; 
     } 
    } 
    } 

    free(table); 
} 

int main(void) 
{ 
    const char* pattern = "acdxdcxecxf"; 
    const char* str = "abdfdaaed"; 
    long score; 
    char* match; 
    char* match2; 

    printf("pattern=\"%s\" str=\"%s\"\n", pattern, str); 
    FindBestMatch(pattern, str, &score, &match); 
    printf("score=%ld (recursive)\n", MatchScore(pattern, str)); 
    printf("score=%ld best match=\"%s\"\n", score, match); 

    // Now repeat with the best match we've just found, 
    // the result must be the same 
    printf("\nRepeating with pattern=best match:\n\n"); 

    printf("pattern=\"%s\" str=\"%s\"\n", match, str); 
    FindBestMatch(match, str, &score, &match2); 
    printf("score=%ld (recursive)\n", MatchScore(match, str)); 
    printf("score=%ld best match=\"%s\"\n", score, match2); 

    free(match); 
    free(match2); 
    return 0; 
} 

출력 : (명백한 부족 이외의 버그가있어 궁금

pattern="acdxdcxecxf" str="abdfdaaed" 
score=14 (recursive) 
score=14 best match="acdfdcaecdf" 

Repeating with pattern=best match: 

pattern="acdfdcaecdf" str="abdfdaaed" 
score=14 (recursive) 
score=14 best match="acdfdcaecdf" 

오류 검사).