首页 > 代码库 > 【编程题目】最长公共字串

【编程题目】最长公共字串

2024-07-17 13:01:22   222人阅读

56.最长公共字串（算法、字符串）。
题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，
则字符串一称之为字符串二的子串。
注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。
请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。
例如：输入两个字符串 BDCABA 和 ABCBDAB，字符串 BCBA 和 BDAB 都是是它们的最
长公共子串，则输出它们的长度 4，并打印任意一个子串。

 

经典动态规划题。

#include <stdio.h>#include <stdlib.h>#include <string.h>void printLCS(char * X, int m, int n, int i, int j, char * B) {    if (i < 0 || j < 0)    {        return;    }    char b = *(B + i * n + j);    if (b == ‘y‘)    {        printLCS(X, m , n, i - 1, j - 1, B);        printf("%c ", X[i]); //先得到的是后面的共同字母，应该在后面打印出来    }    else if (b == ‘u‘)    {        printLCS(X, m , n, i - 1, j, B);    }    else    {        printLCS(X, m , n, i, j - 1, B);    }}int LCS(char * X, char * Y, int m, int n, char * & B) //返回最大公共子串的长度{    int * C = (int *)malloc((m + 1) * (n + 1) * sizeof(int)); //记录每个子问题的最长公共子序列 0-m 0-n    B = (char *)malloc(m * n * sizeof(char)); //标记 1-m 1-n    memset(C, 0, (m + 1) * (n + 1) * sizeof(int)); //初始化为全0    for (int i = 0; i < m; i++)    {        int * crow_1 = C + i * (n + 1); //注意 C 中 i = 1 j = 1 对应 X的X[0] 与 Y的Y[0]        int * crow = C + (i + 1) * (n + 1);        char * brow = B + i * n;  //注意 B 中 i = 0 j = 0 对应 X的X[0] 与 Y的Y[0]        for(int j = 0; j < n; j++)        {            if (X[i] == Y[j])            {                crow[j + 1] = crow_1[j] + 1;                brow[j] = ‘y‘;            }            else            {                crow[j + 1] = (crow_1[j + 1] > crow[j]) ? crow_1[j + 1] : crow[j];                brow[j] = (crow_1[j + 1] > crow[j]) ? ‘u‘ : ‘l‘;            }        }    }    printLCS(X, m, n, m - 1, n - 1, B);    int maxlen = *(C + m * (n + 1) + n);    free(C);    free(B);    return maxlen;}int main(){    char X[7] = {‘A‘,‘B‘,‘C‘,‘B‘,‘D‘,‘A‘,‘B‘};    char Y[6] = {‘B‘,‘D‘,‘C‘,‘A‘,‘B‘,‘A‘};    char * B = NULL;    int l = LCS(X, Y, 7, 6, B);    return 0;}

 


联系
我们