带限制的最长公共子串

Question

我有一个函数可以查找并打印两条 DNA 链之间最长的公共链。不过我想添加一些检查，以便我的程序可以忽略不是基数的字符（“A”、“T”、“C”、“G”） 例如CCAATTFFA和CCAATTKA有共同点：CCAATTA 这是我的代码：

void CommonSubStr(char *X, char *Y, long int m, long int n) {
    long int maxCommonChain = 0;  
    long int end = 0; 
    for (long int i = 0; i < m; i++) {
        for (long int j = 0; j < n; j++) {
            long int currentLength = 0;  
            long int x = i, y = j; 
            while (x < m && y < n && X[x] == Y[y]) {
                currentLength++;
                x++;
                y++;
            }

            if (currentLength > maxCommonChain) {
                maxCommonChain = currentLength;
                end = i + maxCommonChain - 1; 
            }
        }
    }

    if (maxCommonChain == 0) { 
        printf("No common substring found.\n");
        return;
    }

    long int start = end - maxCommonChain + 1; 
    for (long int i = start; i <= end; i++) { 
        if (X[i] == 'A' || X[i] == 'C' || X[i] == 'G' || X[i] == 'T') {
            printf("%c", X[i]);
        }
    }
    printf("\n");
}

任何人都可以帮我添加我应该添加的支票吗？我在

while

循环中尝试了很多检查，但没有一个起作用。

Answer 1

如果您正在处理字符串，则应删除函数的第三个和第四个参数。

由于传递的字符串在函数内不会更改，因此应使用限定符

const

来声明相应的参数。

该函数应该只做一件事：确定公共前缀。所以它应该返回一些结果。例如，结果可以是两个字符串中公共前缀的最后一个相等字符之后的指针。由于您只想输出公共前缀，因此该函数可以返回包含公共前缀的字符串。

在您的函数中，前嵌套的三个循环没有意义。一般来说，您的代码不清楚。与任何不清楚的代码一样，它都会存在逻辑错误。

我可以建议以下函数声明及其定义，如下面的演示程序所示。

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

char * CommonSubStr( const char *s1, const char *s2, const char *s3 )
{
    size_t n = 0;

    for (const char *p1 = s1, *p2 = s2;
        ( p1 = strpbrk( p1, s3 ) ) != NULL && 
        ( p2 = strpbrk( p2, s3 ) ) != NULL && 
        *p1 == *p2;
        ++p1, ++p2)
    {
        ++n;
    }

    char *common_prefix = calloc( n + 1, sizeof( char ) );

    if (common_prefix != NULL)
    {
        char *current = common_prefix;

        for (const char *p1 = s1; n--; )
        {
            p1 = strpbrk( p1, s3 );
            *current++ = *p1++;
        }
    }

    return common_prefix;
}

int main( void )
{
    char *common_prefix = CommonSubStr( "CCAATTFFA", "CCAATTKA", "ATCG" );

    if (common_prefix != NULL) printf( "\"%s\"\n", common_prefix );

    free( common_prefix );
}

程序输出为

"CCAATTA"

如果公共前缀为空，则函数返回空字符串。

现在有了上面所示的函数，就可以轻松编写一个仅输出任何流中两个字符串的公共前缀的函数。

你在这里。

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

FILE * CommonSubStr( const char *s1, const char *s2, const char *s3, FILE *fp )
{
    while(  ( s1 = strpbrk( s1, s3 ) ) != NULL &&
            ( s2 = strpbrk( s2, s3 ) ) != NULL &&
            *s1 == *s2 )
    {
        fputc( *s1, fp );

        ++s1;
        ++s2;
    }

    return fp;

}

int main( void )
{
    fputc( '\n', CommonSubStr( "CCAATTFFA", "CCAATTKA", "ATCG", stdout ) );
}

程序输出为

CCAATTA

可以看到功能实现非常简单。由于使用标准 C 字符串函数，因此只有一个循环

strpbrk

。