diff算法的核心思想是找出两个序列的最长公共子序列（lcs），从而确定最小编辑操作。1.读取文件内容，按行分割构建二维数组；2.使用动态规划计算lcs；3.回溯路径找出差异位置；4.输出或标记差异。实现时需注意效率、内存占用和行匹配精度等问题。
在处理文本文件比较时，比如版本控制系统、文档差异分析等场景，我们经常需要用到类似 diff 的算法来找出两个文件之间的差异。C++作为一门性能较强的编程语言，非常适合实现这类底层逻辑。那么，怎么用C++实现一个基本的文件差异比较呢？核心在于理解并应用 diff 算法的基本思路。
什么是diff算法的核心思想？
diff 算法的目标是找出两个序列之间的最小编辑操作（插入、删除、修改），使得其中一个可以转换成另一个。最常见的实现方式是基于最长公共子序列（LCS）问题的动态规划解法。
举个例子：
有两个字符串 A = "abcde"，B = "acefg"。它们的最长公共子序列是 "ace"。通过找出这个子序列的位置，就可以确定哪些部分是新增的，哪些是被删除的。
在文件比较中，我们可以将每一行为一个元素，构建两个行数组，然后对这两个数组进行 LCS 比较，从而得到差异信息。
立即学习“C++免费学习笔记（深入）”；
如何用C++实现diff功能？
要实现一个基础的 diff 功能，可以按以下步骤来做：
- 读取文件内容，按行分割
- 构建二维数组用于动态规划计算LCS
- 回溯路径找出差异位置
- 输出或标记出不同之处
下面是一个简化的实现思路：
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
// 读取文件到行列表
vector<string> readLines(const string& filename) {
ifstream file(filename);
vector<string> lines;
string line;
while (getline(file, line)) {
lines.push_back(line);
}
return lines;
}
// 构建LCS的DP表
vector<vector<int>> buildLcsTable(const vector<string>& a, const vector<string>& b) {
int m = a.size(), n = b.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (a[i - 1] == b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp;
}
// 回溯找出差异
void findDiff(const vector<string>& a, const vector<string>& b, const vector<vector<int>>& dp) {
int i = a.size(), j = b.size();
while (i > 0 || j > 0) {
if (i > 0 && j > 0 && a[i - 1] == b[j - 1]) {
cout << " " << a[i - 1] << endl; // 相同行
--i; --j;
} else if (j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j])) {
cout << "+ " << b[j - 1] << endl; // 新增行
--j;
} else {
cout << "- " << a[i - 1] << endl; // 删除行
--i;
}
}
}当然，这只是一个简化版本。实际项目中还需要考虑：
- 行内容空格/大小写是否敏感
- 大文件处理（分块加载、内存优化）
- 性能优化（如使用 Myers 差异算法）
实际使用中需要注意的问题
- 效率问题：标准的 LCS 动态规划时间复杂度是 O(n*m)，对于大文件来说可能不够高效。这时候可以考虑更高效的算法，比如 Myers'差分算法，它能在 O(ND) 时间内找到差异。
- 内存占用：如果文件非常大，一次性读入所有行可能导致内存不足。建议按需读取或使用流式处理。
- 行匹配精度：有时候两行内容略有不同但语义相同（比如空格不同），这时候需要做预处理或模糊匹配。
小结一下
实现一个简单的 diff 功能并不难，关键在于理解 LCS 的原理和如何将其应用于行级别的比较。用 C++ 来写的好处是可以精细控制内存和性能，适合嵌入系统或高性能工具开发。
如果你只是想快速实现，也可以参考现有的开源库，比如 google-diff-match-patch 或者直接调用系统的 diff 命令，但在需要定制化功能的时候，自己实现还是很有必要的。
基本上就这些了。 diff 的核心不复杂，但细节容易忽略。
