在c++中实现类似于diff工具的文件内容逐行比对算法，关键在于将文件按行读入内存，再通过动态规划求出两行序列的最长公共子序列，从而推导出哪些行被新增、哪些被删除、哪些保持不变。
基本思路
我们将两个文件分别读取为字符串向量，每一行作为向量的一个元素。然后使用二维数组记录最长公共子序列长度，回溯得到差异信息。
文件读取
使用ifstream按行读取，存入vector<string>中。
差异计算
通过LCS动态规划表，比较行内容是否相等，标记操作类型。
完整代码实现
以下示例展示了一个简化版逐行比对程序：
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
// 读取文件所有行
vector<string> read_lines(const string& path) {
vector<string> lines;
ifstream fin(path);
string line;
while (getline(fin, line)) {
lines.push_back(line);
}
return lines;
}
// 打印差异
void diff(const vector<string>& a, const vector<string>& b) {
int n = a.size(), m = b.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; 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]);
}
}
int i = n, j = m;
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--;
}
}
}
int main() {
auto a = read_lines("file1.txt");
auto b = read_lines("file2.txt");
diff(a, b);
return 0;
}
算法说明
上述代码使用标准LCS方法，时间复杂度为O(n*m)，适合一般文本文件。若文件极大，可考虑分块或基于哈希的优化。
输出含义
- + 表示新增行
- - 表示删除行
- 无符号表示两文件共有行
实际diff工具还会做前缀空白忽略、上下文显示等增强，本文算法可作为核心模块扩展。