华为OJ:，公共字符串计算

公共字符串计算，也称为最长公共子串问题，是指在给定两个串中找到一个字串，使得这个字串在两个原串中出现同时最长。这个问题是近年来常见的字符串处理算法问题之一，有广泛的应用。

在实际应用中，公共字符串计算可以用于文本比对、DNA序列比对、图像匹配等领域。比如在文本比对中，当我们想要找到两份文本的重复部分，就可以使用公共字符串计算算法找到两份文本最长公共子串。在DNA序列比对中，可以通过找到DNA序列中最长公共子串，来比对两个物种的基因差异。

下面介绍两种常见的公共字符串计算算法：

1. 暴力枚举

暴力枚举是最简单的公共字符串计算算法，其基本思路是针对其中一个字符串的每一个字串，在另一个字符串中寻找是否存在相同的字串，然后选取最长的相同字串作为结果。具体算法实现如下：

1. 针对其中一个字符串的每一个字串进行比较；

2. 在另一个字符串中寻找是否存在相同的字串；

3. 如果存在相同字串，则长度加1，并继续比较下一个字符；

4. 如果不存在相同字串，则比较下一个字串，并把长度清零；

5. 重复执行步骤1-4，直到比较完所有字串；

6. 输出最长相同字串。

暴力枚举算法直接遍历所有的子串，并计算它们的长度，因此时间复杂度为$O(n^3)$。在处理大规模数据的时候，效率较低，一般不使用此算法。

2. 动态规划

动态规划是一种更高效的公共字符串计算算法，通过建立一个矩阵来存储已经比较好的公共子串，可以减少比较的次数，从而提高效率。具体算法实现如下：

1. 建立一个二维数组$dp[i][j]$，其中$dp[ i ][ j ]$表示以第一个字符串第i个数字和第二个字符串第j个数字结尾的最长公共字符串长度；

2. 遍历两个字符串，如果第一个字符串的第i个数字和第二个字符串的第j个数字相同，就把$dp[i][j]$赋值为$dp[i-1][j-1]+1$；

3. 如果不同，就把$dp[i][j]$赋值为$0$；

4. 在比较过程中记录最长公共字符串的长度和位置；

5. 输出最长公共字符串。

通过动态规划算法，可以将时间复杂度降到$O(n^2)$，效率非常高，因此在实际应用中更为常用。

综上所述，公共字符串计算是一种实用的字符串处理算法，在文本比对、DNA序列比对、图像匹配等领域有广泛的应用。算法实现上，暴力枚举虽然直观，但时间复杂度较高，因此不适用于大规模数据的处理；而动态规划使用矩阵存储公共子串，大大降低了比较的次数，因此效率更高，更为实用。