题解 | #单词替换#

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;
const int N = 110, P = 13331;

int h[N], p[N], ha[N];

ULL get(int l, int r){
	return h[r] - h[l-1]*p[r-l+1];
}

ULL get_a(int l, int r){
	return ha[r] - ha[l-1]*p[r-l+1];
}
int main(){
	string str;
	
	
	while (getline(cin, str)){
		memset(h, 0, sizeof h);
		memset(ha, 0, sizeof ha);
		memset(p, 0, sizeof p);
		int str_size = str.size();
		str = " " + str;
		
		h[0] = 0;
		p[0] = 1;
		for (int i=1; i<=str_size; i++){
			p[i] = p[i-1] * P;
			h[i] = h[i-1] * P + str[i];
		}

		string a;
		string b;
		cin >> a >> b;
		int a_size = a.size();
		a = " " + a;
		ha[0] = 0;
		for (int i=1; i<=a_size; i++){
			ha[i] = ha[i-1] * P + a[i];
		}
		
		vector<int> tt;
		for (int i=1; i<=str_size; i++){
			if (get_a(1,a_size) == get(i,a_size+i-1) && str[i-1] == ' ' && (str[a_size+i] == '\0' || str[a_size+i]== ' ')){
				tt.push_back(i);
			}
		}
		
		for (int i=1; i<=str_size; i++){
			for (int j=0; j<tt.size(); j++){
				if (i == tt[j]){
					cout << b;
					i = i + a_size;
					break;
				}
			}
			cout <<  str[i];
		}
		puts("");
		getchar();
		
	}
	return 0;
}