使用维基百科和一点思考,你可以编写出类似这样的代码:
#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
long MatchScore(const char* p,
const char* s)
{
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;
}
void FindBestMatch(const char* p,
const char* s,
long* score,
char** match)
{
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];
*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);
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"
我想知道是否有其他错误(除了明显缺乏错误检查之外)。
6^i
种可能的结果。你必须将它们中的每一个都输入到黑盒子中,以告诉您它们的得分,因为一个字符串的得分对于任何其他字符串的得分来说绝对没有意义。这就像查找未排序数组的最大值一样,无法避免地是O(n)(在这种情况下,n == 6 ^ i),唯一可能的例外情况是如果得分以有限类型(例如int
)给出,并且遇到INT_MAX
,你可以提前停止。 - Steve Jessop