原題鏈接

解析

Solution 1

由題意得，能替換的位置一定是 \(s_1\) 能匹配上 \(t_1\) 且 \(s_2\) 能匹配上 \(t_2\) 的位置。替換是否有效就取決于 \(t_1\) 替換掉的子串左右兩邊的串是否和 \(t_2\) 相同。所以可以處理出 \(t_1\) 與 \(t_2\) 的最長公共前綴 (LCP) 與最長公共后綴 (LCS)，利用 KMP 進(jìn)行匹配，根據(jù)匹配到的位置判斷是否計(jì)入答案。具體地，如果匹配到的串能夠覆蓋 \(t_1\) 與 \(t_2\) 不同的區(qū)間，也就是除去 LCP 和 LCS 后剩下的中間部分，則計(jì)入答案，否則說明替換后兩串仍然不同，不計(jì)入答案。

需要預(yù)處理出 \(s\) 的 \(nxt\) 數(shù)組用于匹配。

時(shí)間復(fù)雜度 \(O(nL)\)，期望得分 25~30。

Solution 2

令 \(s_1,s_2\) 真正起作用的那一段子串，也即 \(s_1,s_2\) 分別除去 LCP 和 LCS 的那一段子串然后拼接而成的串為 \(s'\)，稱 \(t_1,t_2\) 經(jīng)過相同處理得到的子串為 \(t'\)。例如，對于 \(s_1=\texttt{xabcx},s_2=\texttt{xadex}\)，其 LCP 為 \(\texttt{xa}\)，LCS 為 \(\texttt{x}\)，中間部分分別為 \(\texttt{bc}\) 和 \(\texttt{de}\)，拼起來就是 \(s'=\texttt{bcde}\)。

對于一對 \(t_1,t_2\)，我們只需要考慮能夠使得 \(s'=t'\) 的 \(s_1,s_2\)，這其實(shí)代表著至多只會有一個(gè)位置能夠匹配。于是，只需要考慮 \(\operatorname{LCP}(s_1,s_2)\) 是否為 \(\operatorname{LCP}(t_1,t_2)\) 的后綴，\(\operatorname{LCS}(s_1,s_2)\) 是否為 \(\operatorname{LCS}(t_1,t_2)\) 的前綴。

這個(gè)問題可以用哈希解決，具體地，可以將 \(s_1,s_2\) 分成 LCP，\(s'\)，LCS 三段進(jìn)行哈希，這樣就可以使用 map 存儲按照 \(s'\) 的分類的 LCP 與 LCS。詢問時(shí)，也對 \(t_1,t_2\) 進(jìn)行三段式哈希，注意需要對 LCP 的每個(gè)后綴，LCS 的每個(gè)前綴進(jìn)行哈希并分別存入一個(gè) map 里。

時(shí)間復(fù)雜度 \(O(nq \log L)\)，期望得分 50。

Solution 3

我們發(fā)現(xiàn)，左右兩部分的匹配其實(shí)是一個(gè)匹配前綴的過程（左邊那部分倒過來就從后綴變成前綴了），所以考慮能否使用字典樹來解決。

首先我們要開兩棵樹，分別存儲所有 \(s_1,s_2\) 的 LCP 的反轉(zhuǎn)和 LCS，記它們?yōu)?\(LT\) 和 \(RT\)。

記 \(\operatorname{LCP}(t_1,t_2)\) 的反轉(zhuǎn)在 \(LT\) 上最終到達(dá)的結(jié)點(diǎn)為 \(lx\)，\(\operatorname{LCS}(t_1,t_2)\) 在 \(RT\) 上最終到達(dá)的結(jié)點(diǎn)為 \(rx\)，\(\operatorname{LCP}(s_1,s_2)\) 的反轉(zhuǎn)在 \(LT\) 上最終到達(dá)的結(jié)點(diǎn)為 \(ly\)，\(\operatorname{LCS}(s_1,s_2)\) 在 \(RT\) 上最終到達(dá)的結(jié)點(diǎn)為 \(ry\)。那么，\(s_1,s_2\) 可以對 \(t_1,t_2\) 作貢獻(xiàn)當(dāng)且僅當(dāng) \(ly\) 是 \(lx\) 的祖先且 \(ry\) 是 \(rx\) 的祖先。也就是說，我們希望統(tǒng)計(jì)有多少個(gè) \(lx\) 的祖先 \(ly\) 對應(yīng)的 \(ry\) 是 \(rx\) 的祖先。于是，我們可以將詢問離線下來在樹上進(jìn)行標(biāo)記，在 \(lx\) 處標(biāo)記 \(rx\) 的值，對 \(LT\) 進(jìn)行 dfs，對于 dfs 過程中遇到的每個(gè) \(ly\)，對 \(RT\) 上與其對應(yīng)的 \(rx\) 的子樹中的點(diǎn)全體加 \(1\)，回溯時(shí)消除影響。對于遇到的每個(gè) \(lx\)，查詢 \(RT\) 上 \(rx\) 的值。查詢和修改的過程可以用樹狀數(shù)組實(shí)現(xiàn)，具體地，先將 \(RT\) 按照 dfs 序編號，記為 \(dfn\)，并處理出每個(gè)點(diǎn)的子樹大小 \(siz\)，然后按照 dfs 序建立樹狀數(shù)組，這樣，子樹修改就變?yōu)樵?\([dfn_x,dfn_x+siz_x)\) 的范圍內(nèi)進(jìn)行修改。

時(shí)間復(fù)雜度 \(O((n+q)\log L)\)，期望得分 100。

代碼

小心 \(s_1=s_2\) 與 \(|t_1|\not=|t_2|\) 的情況。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 5.2e6 + 5,M = 2e5 + 5;
struct Trie{
	int pos[N][26],cnt = 1;
}tl,tr,trm;
int vm[N],mcnt,rootl[M],rootr[M];
vector<int> pos[N];
vector<pii> query[N];
int res[M];
string s1[M],s2[M],t1[M],t2[M];
int dfnl[N],dfnr[N],rcnt,siz[N];
int b[N];
void dfsr(int x){
	dfnr[x] = ++rcnt;
	siz[x] = 1;
	for(int i=0;i<26;i++){
		if(tr.pos[x][i]) dfsr(tr.pos[x][i]),siz[x] += siz[tr.pos[x][i]];
	}
	
}
void add(int x,int k){
	for(;x < N;x += x & -x){
		b[x] += k;
	}
}
int ask(int x){
	int res = 0;
	for(;x;x -= x & -x){
		res += b[x];
	}
	return res;
}
void dfsl(int x){
	for(int i : pos[x]){
		add(dfnr[i],1);
		add(dfnr[i] + siz[i],-1);
	}
	for(int i=0;i<query[x].size();i++){
		pii p = query[x][i];
		res[p.second] = ask(dfnr[p.first]);
	}
	for(int i=0;i<26;i++){
		if(tl.pos[x][i]){
			dfsl(tl.pos[x][i]);
		}
	}
	for(int i : pos[x]){
		add(dfnr[i],-1);
		add(dfnr[i] + siz[i],1);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>s1[i]>>s2[i];
		if(s1[i] == s2[i]) continue;
		int m = (int)s1[i].size() - 1;
		int l = 0,r = m;
		while(s1[i][l] == s2[i][l]) l++;
		while(s1[i][r] == s2[i][r]) r--; 
		string s = s1[i].substr(l,r - l + 1) + s2[i].substr(l,r - l + 1);
		int mpos,rpos;
		int p = 1;
		for(int j=0;j<s.size();j++){
			if(!trm.pos[p][s[j] - 'a']) trm.pos[p][s[j] - 'a'] = ++trm.cnt;
			p = trm.pos[p][s[j] - 'a'];  
		}
		if(!vm[p]){
			vm[p] = ++mcnt;
			rootl[vm[p]] = ++tl.cnt;
			rootr[vm[p]] = ++tr.cnt;
		}
		mpos = vm[p];
		p = rootr[mpos];
		for(int j=r + 1;j<=m;j++){
			if(!tr.pos[p][s1[i][j] - 'a']) tr.pos[p][s1[i][j] - 'a'] = ++tr.cnt;
			p = tr.pos[p][s1[i][j] - 'a']; 
		}
		rpos = p;
		p = rootl[mpos];
		for(int j=l - 1;j>=0;j--){
			if(!tl.pos[p][s1[i][j] - 'a']) tl.pos[p][s1[i][j] - 'a'] = ++tl.cnt;
			p = tl.pos[p][s1[i][j] - 'a']; 
		}
		pos[p].push_back(rpos);
	}
	for(int i=1;i<=mcnt;i++){
		dfsr(rootr[i]);
	}
	for(int i=1;i<=q;i++){
		cin>>t1[i]>>t2[i];
		if(t1[i].size() != t2[i].size()) continue;
		int m = t1[i].size() - 1;
		int l = 0,r = m;
		while(t1[i][l] == t2[i][l]) l++;
		while(t1[i][r] == t2[i][r]) r--; 
		string t = t1[i].substr(l,r - l + 1) + t2[i].substr(l,r - l + 1);
		int p = 1;
		bool flag = true;
		int mpos,rpos;
		for(int j=0;j<t.size();j++){
			if(!trm.pos[p][t[j] - 'a']){
				flag = false;
				break;
			}
			p = trm.pos[p][t[j] - 'a'];
		}
		if(!flag) continue;
		mpos = vm[p];
		p = rootr[mpos];
		for(int j=r + 1;j<=m;j++){
			if(!tr.pos[p][t1[i][j] - 'a']){
				break;
			}
			p = tr.pos[p][t1[i][j] - 'a'];
		}
		rpos = p;
		p = rootl[mpos];
		for(int j=l - 1;j>=0;j--){
			if(!tl.pos[p][t1[i][j] - 'a']){
				break;
			}
			p = tl.pos[p][t1[i][j] - 'a'];
		}
		query[p].push_back({rpos,i});
	}
	for(int i=1;i<=mcnt;i++){
		dfsl(rootl[i]);
	}
	for(int i=1;i<=q;i++){
		cout<<res[i]<<"\n";
	}
	return 0;
}