题目

官网链接：TUOJ

参考：CCF-CSP第35次认证第三题——补丁应用【C++满分题解】-CSDN博客

本文仅对上文做一点补充说明以及记录感悟

补充说明

正则表达式

此题如果会用正则表达式，对补丁块第一行的处理会方便很多：

参考：

C++正则表达式 - cpluspluser - 博客园 https://www.cnblogs.com/coolcpp/p/cpp-regex.html

感悟：题解看不懂怎么办

题解中最不好理解的可能是对每个补丁块进行处理的部分，强烈建议静下心来，对着案例1，在纸上推导一遍，相信会有豁然开朗的感觉

代码

【对上面的代码按照自己的习惯进行了改写，但是逻辑基本一致】：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

struct patchBlock{
	int or_n; //origial_NN 可能的起始 
	int or_m; //original_MM 原文长度 
	int m; //改后长度 
	vector<string> or_cont; //original_content
	vector<string> n_cont; //new_content
};

bool parseheader(const string& header, int& or_n, int& or_m, int& n, int& m)
{
	regex pattern(R"(^@@ -(\d+),(\d+) \+(\d+),(\d+) @@$)");
	smatch match;
	if(!regex_match(header,match,pattern)) return false;
	or_n=stoi(match[1]); 
	or_m=stoi(match[2]);
	n=stoi(match[3]);
	m=stoi(match[4]);
	return true;
} 

void p_error() //print_error
{
	cout<<"Patch is damaged."<<endl;
	return;
}

bool cmp(int a,int b)
{
	if(abs(a)!=abs(b)) return abs(a)<abs(b);
	return a<b;
}

void solve()
{
	int n; cin>>n;
	cin.get();
	vector<string> or_line; //original_line
	for(int i=0;i<n;i++)
	{
		string s;
		getline(cin,s);
		or_line.push_back(s);
	}
	vector<string> patchline;
	string s;
	while(getline(cin,s))
	{
		if(!(s[0]=='#')) patchline.push_back(s);
	}
	vector<patchBlock> blocks;
	for(int i=0;i<patchline.size();)
	{
		if(patchline[i].substr(0,2)=="@@")	
		{
			string header=patchline[i++];
			vector<string>blockline;
			
			while(i<patchline.size()&&patchline[i].substr(0,2)!="@@")
				blockline.push_back(patchline[i++]);
			
			int or_n, or_m, nn, m;
			if(!parseheader(header, or_n, or_m,nn, m))
			{
				cout<<"Patch is damaged."<<endl;
				return;
			}
			
			vector<string>or_content, n_content; // original_content new_content
			for(auto& line: blockline )
			{
				char perfix=line[0]; //第一个字符 
				if(perfix!=' '&&perfix!='+'&&perfix!='-')  //WARN
				{
					cout<<"Patch is damaged."<<endl;
					return;
				}
				string content=line.substr(1); //去除+- 
				if(perfix=='-'||perfix==' ') or_content.push_back(content);
				if(perfix=='+'||perfix==' ') n_content.push_back(content);			
			}
			if(or_content.size()!=or_m||n_content.size()!=m)
			{
				cout<<"Patch is damaged."<<endl;
				return;
			}
			if(!blocks.empty()) //不是第一个 
			{
				auto lastblock=blocks.back(); //最后一个块
				if(or_n < lastblock.or_n+lastblock.or_m)
				{
					p_error();
					return;
				}
			}
			blocks.push_back(patchBlock{or_n,or_m,m, or_content,n_content});
		}
		else i++;
	}
			
	if(blocks.empty()){
		p_error();
		return;
	}
    
    // 处理补丁块
	int deltasum=0;
	int pre_N=0;
	int pre_M=0;
	
	for(int idx=0;idx<blocks.size();idx++)
	{
		patchBlock& block=blocks[idx];
		int N=block.or_n + deltasum;
		int M=block.or_m;
		vector<int> valid_delta;
		
		for(int delta=-(M-1);delta<M;delta++) //delta
		{
			int s1=N+delta; //从1开始的数 的下标//起始行数 
			if(s1<1) continue;
			if(s1+M-1>or_line.size()) continue;
			if(idx>0)
				if(s1<=pre_N+pre_M-1) continue; //warn <=
			
			bool match=1;
			for(int i=0;i<M;i++)
			{
				if(or_line[s1-1+i]!=block.or_cont[i])
				{
					match=0;
					break; //warn：要继续处理，不能return 
				}
			}
			if(match) valid_delta.push_back(delta);
		}
		//WARN 判空
		if(valid_delta.empty()) 
		{
			p_error();
			return;
		}
		
		sort(valid_delta.begin(),valid_delta.end(),cmp);
		int delta=valid_delta[0];
		pre_N=N+delta; //更新上一块实际起点 //WARN:not orignal_n
		
		int s0=N +delta-1;//从0开始算  的下标 //WARN: N 
		or_line.erase(or_line.begin()+s0,or_line.begin()+s0+M);
		or_line.insert(or_line.begin()+s0,block.n_cont.begin(),block.n_cont.end());//WARN 
		
		delta+=block.m-block.or_m; //该块对后续块的偏移：加上替换带来的移动 
		deltasum+=delta;
		pre_M=block.m; //更新上一块实际长度 
	} 
	
	for(auto& line:or_line) cout<<line<<endl;  
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;	
}