【算法笔记】AC自动机+可持久化线段树解决大字符集的问题

问题：

这里的trie树和普通的不一样，因为串长最多有O(n^2),而不是以前的O(n)。姑且把它叫做广义Trie树

这道题目显然是裸的AC自动机，然而字符集很大。
这里不能直接map，用一般的均摊AC自动机（求fail的时候用while跳）。这样复杂度错误的

要用可持久化线段树维护trans数组
下面的代码只是一个思路。以前写这道题的代码找不到了，，，

void build(){		
		hh = tt = 0;
		for (int t = 0 ; t < maxchar ; t++) if ( nxt[0][t] ) q[tt++] = nxt[0][t] , trans[0][t] = nxt[0][t];
		while ( hh < tt ){
			int x = q[hh++];
			for (int t = 0 ; t < maxchar ; t++){
				if ( nxt[x][t] ){
					fail[nxt[x][t]] = trans[fail[x]][t] , q[tt++] = nxt[x][t]; //字符集很大，可持久化trans数组
					trans[x][t] = nxt[x][t];
				}	
				else trans[x][t] = trans[fail[x]][t];
			}
		}
		for (int i = 1 ; i <= tot ; i++) adde(fail[i],i);
		dfs(0);
	}