2021年寒假每日一題，2017~2019年的省賽真題，
本文內容由倪文迪（華東理工大學計算機系軟體192班）和羅勇軍老師提供，

后面的每日一題，每題發一個新博文，請大家看博客目錄：https://blog.csdn.net/weixin_43914593

1、題目描述

??2017年藍橋杯軟體類省賽C++大學A組第6題“最大公共子串”，
??一道代碼填空題，八成也是送分題，
??因為不難，羅老師就再做一次，

最大公共子串長度問題就是：
求兩個串的所有子串中能夠匹配上的最大長度是多少，

比如：“abcdkkk” 和 “baabcdadabc”，
可以找到的最長的公共子串是"abcd",所以最大公共子串長度為4，

下面的程式是采用矩陣法進行求解的，這對串的規模不大的情況還是比較有效的解法，

請分析該解法的思路，并補全劃線部分缺失的代碼，

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

#define N 256
int f(const char* s1, const char* s2)
{
	int a[N][N];
	int len1 = strlen(s1);
	int len2 = strlen(s2);
	int i,j;
	
	memset(a,0,sizeof(int)*N*N);
	int max = 0;
	for(i=1; i<=len1; i++){
		for(j=1; j<=len2; j++){
			if(s1[i-1]==s2[j-1]) {
				a[i][j] = __________________________;  //填空
				if(a[i][j] > max) max = a[i][j];
			}
		}
	}
	
	return max;
}

int main()
{
	printf("%d\n", f("abcdkkk", "baabcdadabc"));
	return 0;
}

注意：只提交缺少的代碼，不要提交已有的代碼和符號，也不要提交說明性文字，

2、題解

??又是一道常見DP，果然又是送分題，

??注意此題是“最大公共子串”，不是“最大公共子序列”，子序列和子串是不同的概念，子串的元素在原序列中是連續的，子序列不用連續，題目的例子中子串“abcd”是連續的字符，

?? a [ ] [ ] a[][] a[][]就是狀態轉移矩陣，DP的狀態轉移矩陣一般寫作 d p [ ] [ ] dp[][] dp[][]，題目里寫成 a [ ] [ ] a[][] a[][]有那么一點點迷惑作用，
??狀態 a [ i ] [ j ] a[i][j] a[i][j]的含義是：以 s 1 [ i ] s_1[i] s1?[i]和 s 2 [ j ] s_2[j] s2?[j]為結尾的兩個子串 s 1 [ 0 ] s_1[0] s1?[0] ~ s 1 [ i ] s_1[i] s1?[i]和 s 2 [ 0 ] s_2[0] s2?[0] ~ s 2 [ j ] s_2[j] s2?[j]，它們的公共子串的長度，
??遍歷所有的 i 、 j i、j i、j，其中最大的 a [ i ] [ j ] a[i][j] a[i][j]就是答案，
??狀態如何轉移？討論兩種情況：
??（1）若 s 1 [ i ] ! = s 2 [ j ] s_1[i] != s_2[j] s1?[i]!=s2?[j]，那么 a [ i ] [ j ] = 0 a[i][j]=0 a[i][j]=0；
??（2）若 s 1 [ i ] = = s 2 [ j ] s_1[i]==s_2[j] s1?[i]==s2?[j]，那么就看前一個字符是否相等，有 a [ i ] [ j ] = a [ i ? 1 ] [ j ? 1 ] + 1 a[i][j] = a[i-1][j-1] + 1 a[i][j]=a[i?1][j?1]+1，
??其中（1）已經在memset把a[][]初始化為0時實作了，所以代碼填空就是完成（2）：

	a[i][j] = a[i-1][j-1] + 1;

3、擴展

??子串問題比子序列問題簡單那么一丟丟，當然子序列問題也很簡單，
??參考這篇博文，詳細介紹了“最大公共子序列”：
??DP概述和常見DP面試題
https://blog.csdn.net/weixin_43914593/article/details/105444090