C++实现：求两个字符串的最长公共子串

本资源是一份C++程序代码，用于求解两个给定字符串的最长公共子序列（Longest Common Subsequence, LCS）。在编程中，最长公共子序列是指不考虑字符顺序，但保持字符集相同的最小子序列。这段代码的核心功能是通过动态规划算法实现对字符串"str1"和"str2"的最长公共字串的查找。 首先，程序导入了必要的头文件，如<iostream>和<string.h>，并使用命名空间std。定义了一个常量M100用于限制字符串的最大长度。接下来，定义了一个名为LCS的函数，它接收两个字符数组作为输入参数。 LCS函数的主要逻辑如下： 1. 获取两个输入字符串的长度，并为存储最长公共字串结果分配内存。 2. 初始化一个字符指针c，长度为右字符串的长度，所有元素初始化为0。 3. 使用两层嵌套循环遍历两个字符串： - 外层循环i遍历左字符串，内层循环j从右向左遍历右字符串。 - 如果当前字符相同，根据之前子问题的结果更新最长公共子串的长度，并将字符添加到结果字符串c中。 - 如果字符不同，则设置c[j]为0，表示没有公共字符。 - 在每次更新过程中，记录当前最长公共子串的长度（len）和结束位置（end）。 4. 计算起始位置（start），即结果字符串的起始索引，然后动态分配一个新的字符数组p来存储结果。 5. 将结果字符串p拷贝回原地，并在末尾添加空字符'\0'以表示字符串结束。 6. 最后，在main函数中，用户输入两个字符串，调用LCS函数并输出结果。 通过这个程序，输入两个字符串如"a=abcrrrerads"和"b=afdabcssbcrrresswrds"，可以找到它们的最长公共字串"bcrrre"。这个C++程序展示了如何运用动态规划的思想解决字符串处理中的经典问题，对于学习和理解字符串算法具有很好的参考价值。