题解 | 查找两个字符串a,b中的最长公共子串

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

/*一维动态规划，定义一个数组dp[shortlen][2]，[i][0],代表短字符串中最后出现目标字符串（即最长公共子串）的位置，[i][1],代表目标字符串（即最长公共子串）的长度,i从0一直遍历到shortlen，时间复杂度为O(2*M)*/
int main() {
    char str1[301];
    char str2[301];
    char *pshort,*plong,tempchar;
    int i,j,shortlen,dstlen;

    scanf("%s",str1);
    scanf("%s",str2);

    pshort=str1;
    plong=str2;
    if(strlen(str1)>strlen(str2))
    {
        pshort=str2;
        plong=str1;
    }   
    shortlen=strlen(pshort);
    int dp[shortlen][2];                /*[i][0],代表短字符串中最后出现目标字符串（即最长公共子串）的位置，[i][1],代表目标字符串（即最长公共子串）的长度*/

    if(strchr(plong,pshort[0]))
    {
        dp[0][0]=0;
        dp[0][1]=1;
    }
    else {
        dp[0][1]=dp[0][0]=0;
    }

    for(i=1;i<shortlen;i++)
    {
        if((dp[i-1][0]+dp[i-1][1])==i)
        {
            tempchar = pshort[i+1];
            pshort[i+1]='\0';
            if(strstr(plong,pshort+dp[i-1][0]))
            {
                dp[i][0]=dp[i-1][0];
                dp[i][1]=dp[i-1][1]+1;
            }
            else 
            {
                dp[i][0]=dp[i-1][0];
                dp[i][1]=dp[i-1][1];
            }
            pshort[i+1]=tempchar;
        }
        else 
        {   
            tempchar = pshort[i+1];
            pshort[i+1]='\0';
            //if(strstr(plong,pshort+i-dp[i-1][0]+1))
            if(strstr(plong,pshort+i-dp[i-1][1]+1))  //更新目标字符串的位置
            {
                dp[i][0]=i-dp[i-1][1]+1;
                dp[i][1]=dp[i-1][1];
            }
            else 
            {
                dp[i][0]=dp[i-1][0];
                dp[i][1]=dp[i-1][1];
            }
            pshort[i+1]=tempchar;        
        }
    }

    dstlen=dp[shortlen-1][1];
    for(i=0;i<shortlen;i++)
    {
        tempchar = pshort[i+dstlen];
        pshort[i+dstlen]='\0';
        if(strstr(plong,pshort+i))
        {
            printf("%s",pshort+i);
            return 0;
        }
        pshort[i+dstlen]=tempchar;
    }

    return 0;
}