数据结构求公共子串问题

来源：百度知道 编辑：UC知道 时间：2024/09/24 00:28:23
串<1,0,0,1,0,1,0,1>与<0,1,0,1,1,0,1,1>的最长公共子串序列长度为多少？这道题的答案是6请问是怎么得到的能帮我解释一下吗？请细致些非常感谢！
这是一道选择题，我想没有这么复杂我就想知道是怎么比的能用文字叙述一下吗？

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main()
{
string str1,str2;
while (cin>>str1>>str2)
{
int m=str1.size(),n=str2.size();
int**ptr=new int*[m+1];
for (int i=0;i<=m;i++)
{
ptr[i]=new int [n+1];
}
for (int i=0;i<m;i++)
ptr[i][0]=0;
for (int i=0;i<n;i++)
ptr[0][i]=0;
for (int i=1;i<=m;i++)
{
for (int j=1;j<=n;j++)
{
if(str1.at(i-1)==str2.at(j-1))
{ptr[i][j]=ptr[i-1][j-1]+1;cout<<ptr[i][j]<<ends;}
else
{ptr[i][j]=ptr[i-1][j]>ptr[i][j-1]?ptr[i-1][j]:ptr[i][j-1];cout<<ptr[i][j]<<ends;}
}
}
cout<<ptr[m][n]<<endl;
}

return 0;
}

用的是动态规划的知识；

思想是这样的：