北京网站备案在哪,wordpress支付功能,咋样做班级主页网站,天津滨海新区大爆炸Problem Description 从一个给定的串中删去#xff08;不一定连续地删去#xff09;0个或0个以上的字符#xff0c;剩下地字符按原来顺序组成的串。例如#xff1a;“ ”#xff0c;“a”#xff0c;“xb”#xff0c;“aaa”#xff0c;“bbb”#xff0c;“xabb”不一定连续地删去0个或0个以上的字符剩下地字符按原来顺序组成的串。例如“ ”“a”“xb”“aaa”“bbb”“xabb”“xaaabbb”都是串“xaaabbb”的子串。例子中的串不包含引号。 编程求N个非空串的最长公共子串的长度。限制2N100N个串中的字符只会是数字01…9或小写英文字母ab…z每个串非空且最多含100个字符N个串的长度的乘积不会超过30000。Input
文件第1行是一个整数T表示测试数据的个数1T10。接下来有T组测试数据。各组测试数据的第1行是一个整数Ni表示第i组数据中串的个数。各组测试数据的第2到N1行中每行一个串串中不会有空格但行首和行末可能有空格这些空格当然不算作串的一部分。Output
输出T行每行一个数第i行的数表示第i组测试数据中Ni个非空串的最长公共子串的长度。Example Input 1
3
ab
bc
cd Example Output 0 求解最长公共子串问题利用动态规划思想不管是否理解动态规划把这个原理弄明白就行。 首先直接给出一个例子 主串str[7]”ABCBDAB” 子串substr[6]”BDCABA” 求最长公共子串 我们先不考虑如何实现这个先来分析这个结果为多少通过比较容易得出当子串为BDAB时候最长公共子串的值为4。 好了现在我们一起来分析算法了 首先定义一个sum[][]二维数组初始化为0行表示主串的字符列表示子串的字符那么sum[i][j表示主串的第i(从一开始数)个字符与子串的j1个字符的最长公共子串的结果值最后sum[7][6]的值就是最长公共子串的结果。 首先主串中的A与子串匹配当子串数组的下标为3、5时候匹配首先分析3当下标3与其主串的首字符匹配那么此时sum[1][4]1,此时的sum[1][5]sum[1][6]1(注意因为匹配到这里的时候最长公共子串仍然为1) 主串继续匹配str[0]substr[5]此时sum[2][6]1主串往后移动str[1]substr[0] 则sum[2][x]1x1,,继续移动str[2]str[2]此时sum[3][3]sum[2][2]12后面一以此类推... #includeiostream
#includestdio.h
#includealgorithm
#includecstring
using namespace std;
int main()
{char x[505],y[505];int sum[505][505],i,j,len1,len2;while(gets(x)){gets(y);len1strlen(x);len2strlen(y);memset(sum,0,sizeof(sum));for(i1;ilen1;i){for(j1;jlen2;j){if(x[i-1]y[j-1])sum[i][j]sum[i-1][j-1]1;elsesum[i][j]max(sum[i-1][j],sum[i][j-1]);}}printf(%d\n,sum[len1][len2]);}return 0;
}/*超时作法
#includeiostream
#includestdio.h
#includealgorithm
#includecstring
using namespace std;int main()
{while(1){ char str[500],substr[500];int a[500]{0},b[500]{0};gets(str);gets(substr);for(int i0;istrlen(substr);i){for(int j0;jstrlen(str);j){if(str[j]substr[i]){a[j]1;//标记 b[j]1;}}}for(int i1;istrlen(str);i){for(int j0;ji;j){if(str[i]str[j](a[i])(a[j])b[i]b[j]1){b[i]b[j]1;}}} int ans-1;for(int i0;istrlen(str);i){if(ansb[i])ansb[i];}coutansendl;}return 0;
}*/
