T497772 QDLOI-R2-T3 Define

T497772 QDLOI-R2-T3 Define题解

这是一道经典（也许也并不是）的字符串题目。我之所以说它很经典是应为我多次在这上翻车。。。

思路：

1、读入时存储修改与目标的对应关系

2、使用查找函数find进行查找，直到全部更改完成后为止

3、一定注意：需按照题目给定的对应顺序进行更改操作

第一次（40分）

问题在于被更改的字符串与目标字符串的下标没有对上，所以给改后出现了空字符

第二次（80分）

这里我可以给大家看看我当时的代码：

#include<iostream>
#include<string>
using namespace std;
const int MAXN=1e4+10;
int n,m;
string change[MAXN],to[MAXN];
int main(){cin>>n>>m;for(int i=1;i<=n;i++){string a,b,c;cin>>a>>b>>c;if(a=="#define"){change[i]=b;to[i]=c;}else{change[i]=c;to[i]=b;}}for(int i=1;i<=m;i++){string s;cin>>s;for(int i=1;i<=n;i++){if(change[i].size()>s.size())continue;if(change[i].size()==s.size()&&change[i]!=s)continue;while(s.find(change[i])<=s.size()){int p=s.find(change[i]);for(int j=p;j<p+change[i].size();j++){s[j]=to[i][j-p];}}}cout<<s<<" ";}return 0;
}

可以注意到“while(s.find(change[i])<=s.size())”
这里就是我犯下的错误

我写的是：只要还能找到就继续找。而忽略了一种可能，就是我的替换前字符串和替换后字符串一致。所以，当最后一个数据点出现这种情况后会一直找，最终TLE

第三次（AC）

修改完前两个问题后，我的代码终于AC了

#include<iostream>
#include<string>
using namespace std;
const int MAXN=1e4+10;
int n,m,k=1;
string change[MAXN],to[MAXN];
int main(){cin>>n>>m;for(int i=1;i<=n;i++){string a,b,c;cin>>a>>b>>c;if(b==c)continue;//如果更改字串与目标字串相同直接跳过if(a=="#define"){change[k]=b;to[k++]=c;}else{change[k]=c;to[k++]=b;}}k--;for(int i=1;i<=m;i++){string s;cin>>s;for(int i=1;i<=k;i++){if(change[i].size()>s.size())continue;if(change[i].size()==s.size()&&change[i]!=s)continue;while(s.find(change[i])<=s.size()){int p=s.find(change[i]);for(int j=p;j<p+change[i].size();j++){s[j]=to[i][j-p];//同步下标}}}cout<<s<<" ";}return 0;
}