先帝创业未半而中道崩殂，后面忘了

Difficulty：5.3 / Easy+

Tag：Trie，树状数组

省选试机时挑的题，总共写了 1h（试机时）+30min（刚刚写的）。

这个转化不用说了吧还是说一下吧。就是可以转化成两个串相同前后缀加上中间那一坨，然后查询一个转化后的模式串可以包多少个转化后的文本串。

这个显然可以哈希记录中间那一坨，然后对每一个中间那一坨，分别给前后缀建一个 Trie。

你说得对，但是哈希还是太吃操作和码量了。

办法还是有的。就是把中间那一坨拼接在前后缀前面，当成判断的一部分。这样就只需要建两个 Trie 了。

我实现的时候因为前缀需要倒序遍历，所以其实是拼在后面再反转的，也相当于拼在前面了。

然后我们对两棵 Trie dfs，然后查询文本串所在的 dfn 区间，就转化成一个矩形加单点查问题了。这不神奇吗。

这个显然可以扫扫扫。

字典树空间一开始以为要开 $2L+2n$，但后来发现 $L=\sum T_1+T_2=2\sum T_1$，所以开 $L+2n$ 就足够了。

namespace cjdst{
	const int N = 200000, M = 6000000, B = 27;
	
	std::string a1[N + 5], a2[N + 5];
	
	namespace Trie{
		char tr[M + 5][2];
		int son[M + 5][B][2];
		int indfn[M + 5][2], outdfn[M + 5][2];
		int ctnode[2];
		int new_node(char c, int id){
			tr[++ctnode[id]][id] = c;
			return ctnode[id];
		}
		int insert(std::string s, int id){
			int cur = 0;
			for(char c:s){
				if(!son[cur][c - 'a'][id]){
					son[cur][c - 'a'][id] = new_node(c, id);
				}
				cur = son[cur][c - 'a'][id];
			}
			return cur;
		}
		void dfs(int cur, int id, int &curdfn){
			indfn[cur][id] = (++curdfn);
			for(int i = 0; i < B; i++){
				if(son[cur][i][id]) dfs(son[cur][i][id], id, curdfn);
			}
			outdfn[cur][id] = curdfn;
		}
		int find(std::string s, int id){
			int cur = 0;
			for(char c:s){
				if(!son[cur][c - 'a'][id]) return 0;
				cur = son[cur][c - 'a'][id];
			}
			return cur;
		}
	}
	
	namespace Fenwick_Tree{
		int fenwick[M + 5];
		void modify(int idx, int val){
			for(int i = idx; i <= M; i += (i & (-i))){
				fenwick[i] += val;
			}
		}
		int query(int idx){
			int ans = 0;
			for(int i = idx; i; i -= (i & (-i))){
				ans += fenwick[i];
			}
			return ans;
		}
	}
	
	using namespace Trie;
	using namespace Fenwick_Tree;
	
	struct node{
		int tmp, l1, r1, l2, r2, id;
		bool operator < (const node &b) const{
			if(l1 == b.l1) return tmp < b.tmp;
			return l1 < b.l1;
		}
		bool operator > (const node &b) const{
			return r1 > b.r1;
		}
	}q[N * 8 + 5];
	int ctq;
	int ans[N + 5];
	
	void solve(){
		int n, m;
		std::cin >> n >> m;
		
		for(int i = 1; i <= n; i++){
			std::cin >> a1[i] >> a2[i];
		}
		
		for(int i = 1; i <= m; i++){
			std::string x, y;
			std::cin >> x >> y;
			if(x.size() != y.size()){
				continue;
			}
			int l = 1, r = x.size();
			x = " " + x, y = " " + y;
			while(x[l] == y[l]) l++;
			while(x[r] == y[r]) r--;
			std::string ll = x.substr(1, l - 1) + '{' + x.substr(l, r - l + 1) + '{' + y.substr(l, r - l + 1);
			std::string rr = x.substr(l, r - l + 1) + '{' + y.substr(l, r - l + 1) + '{' + x.substr(r + 1, 10000000);
			std::reverse(ll.begin(), ll.end());
			int xx = insert(ll, 0), yy = insert(rr, 1);
			q[++ctq] = {2, xx, xx, yy, yy, i};
		}
		
		int curdfn = 0;
		dfs(0, 1, curdfn);
		curdfn = 0;
		dfs(0, 0, curdfn);
		
		for(int i = 1; i <= ctq; i++){
			q[i] = {2, indfn[q[i].l1][0], indfn[q[i].l1][0], indfn[q[i].l2][1], indfn[q[i].l2][1], i};
		}
		for(int i = 1; i <= n; i++){
			std::string x = a1[i], y = a2[i];
			if(x == y) continue;
			int l = 1, r = x.size();
			x = " " + x, y = " " + y;
			while(x[l] == y[l]) l++;
			while(x[r] == y[r]) r--;
			std::string ll = x.substr(1, l - 1) + '{' + x.substr(l, r - l + 1) + '{' + y.substr(l, r - l + 1);
			std::string rr = x.substr(l, r - l + 1) + '{' + y.substr(l, r - l + 1) + '{' + x.substr(r + 1, 10000000);
			std::reverse(ll.begin(), ll.end());
			int id1 = find(ll, 0), id2 = find(rr, 1); 
			if(!id1 || !id2) continue;
			q[++ctq] = {1, indfn[id1][0], outdfn[id1][0], indfn[id2][1], outdfn[id2][1], 0};
		}
		
		std::sort(q + 1, q + ctq + 1);
		
		int l = 1;
		std::priority_queue <node, std::vector <node>, std::greater <node>> qq;
		for(int i = 1; i <= curdfn; i++){
			while(!qq.empty() && qq.top().r1 < i){
				modify(qq.top().l2, -1);
				modify(qq.top().r2 + 1, 1);
				qq.pop();
			}
			while(l <= ctq && q[l].l1 <= i){
				if(q[l].tmp == 2){
					ans[q[l].id] = query(q[l].l2);
				}else{
					modify(q[l].l2, 1);
					modify(q[l].r2 + 1, -1);
					qq.push(q[l]);
				}
				l++;
			}
		}
		
		for(int i = 1; i <= m; i++){
			std::cout << ans[i] << '\n';
		}
	}
}

时间复杂度：$O(|\Sigma|L+(n+q)\log L)$。