哈希倒闭了怎么办/jk

书接上回。

发现中考英语作文没拿满分，严肃意识到自己不会字符串。

由于现在是上午，所以只学一个算法，剩下一个放在下午。 都快打 CF 了我还没学我怎么这么区。 第二天下午也是下午。 ACAM 我好像学过了，那我就是区。

Manacher

将每个字符两边用一个滚木包裹，使得所有回文串长度都为奇数。

考虑维护此时每个 $i$ 为中心的最长回文子串端点与 $i$ 的距离 $P_i$。则原串答案显然为 $\frac{(2P_i+1)-1}{2}=P_i$。

考虑维护目前小于 $i$ 为中心的最长回文子串中右端点最大值 $r$ 及其中心 $mid$。

由回文串定义（关于中心对称）得，$i$ 为中心，$\min\{r,i+P_{mid-(i-mid)}\}$ 为右端点的串一定回文。

然后暴力扩展，更新 $mid$ 与 $r$。每次暴力扩展一定会使 $r$ 移动 $1$，而 $r$ 一共只会移动 $n$ 次，所以时间复杂度为 $O(n)$。

namespace cjdst{
    void solve(){
		std::string a;
		std::cin >> a;
		int n = a.size() * 2 + 1;
		std::string b = "  ";
		for(char c:a){
			b += c;
			b += ' ';
		}
		std::swap(a, b);
		std::vector <int> p(n + 5);
		int mid = -1, r = 0;
		for(int i = 1; i <= n; i++){
			if(i > r){
				mid = r = i;
			}
			p[i] = std::min(r - i, p[mid * 2 - i]);
			while(i - p[i] > 1 && i + p[i] < n && a[i - p[i] - 1] == a[i + p[i] + 1]){
				p[i]++;
			}
			if(i + p[i] > r){
				mid = i, r = i + p[i];
			}
		}
		std::cout << *std::max_element(p.begin() + 1, p.begin() + n + 1) << '\n';
	}
}

时间复杂度：$O(n)$。

ACAM

学过了，但还是讲一下。

等一下，我真的会吗。

不管了，这个背个板子就行了，然后知道一个点表示一种匹配状态就行了。

namespace cjdst{
	const int N = 200000, M = 26;
	int son[N + 5][M], fail[N + 5], ans[N + 5], in[N + 5], mp[N + 5];
	int n;
	std::string s[N + 5], t;
	int ctnode, ctstr;
	void insert(int idx){
		int cur = 0;
		for(char c:s[idx]){
			if(!son[cur][c - 'a']){
				son[cur][c - 'a'] = (++ctnode);
			}
			cur = son[cur][c - 'a'];
		}
		mp[idx] = cur;
	}
	
	void build(){
		std::queue <int> q;
		for(int i = 0; i < M; i++){
			if(son[0][i]) q.push(son[0][i]);
		} 
		while(!q.empty()){
			int head = q.front();
			q.pop();
			for(int i = 0; i < M; i++){
				if(!son[head][i]){
					son[head][i] = son[fail[head]][i];
				}else{
					fail[son[head][i]] = son[fail[head]][i];
					q.push(son[head][i]);
				}
			}
		}
	}
	
	void query(){
		int cur = 0;
		for(char c:t){
			cur = son[cur][c - 'a'];
			ans[cur]++; 
		}
		for(int i = 1; i <= ctnode; i++){
			in[fail[i]]++;
		}
		std::queue <int> q;
		for(int i = 1; i <= ctnode; i++){
			if(!in[i]) q.push(i); 
		}
		while(!q.empty()){
			int head = q.front();
			q.pop();
			ans[fail[head]] += ans[head];
			if(!(--in[fail[head]])) q.push(fail[head]);
		}
	}
	
	void solve(){
		std::cin >> n;
		for(int i = 1; i <= n; i++){
			std::cin >> s[i];
			insert(i);
		}
		build();
		std::cin >> t;
		query();
		for(int i = 1; i <= n; i++){
			std::cout << ans[mp[i]] << '\n';
		}
	}
}

时间复杂度：$O(\sum |S||\Sigma|+|T|)$

P2292

Difficulty：4.6 / Easy

Tag：ACAM

考虑 DP。$dp_i$ 表示前 $i$ 个字符是否可以完全匹配。则有 $dp_i=\text{or}_{t_{[i\sim j]}=A_k}\{dp_{j}\}$。使用 AC 自动机判断是否完全匹配，这么转移复杂度是 $O(nm|T|)$ 的。注意到可以压位记录每个节点匹配状态以及当前最后 $|S|$ 项 $dp$ 值，然后直接取或即可知道是否有符合条件，优化至 $O(m|T|)$。理论上如果 $|S|$ 足够大，这个可以用 bitset 做到 $O(\frac{m|S||T|}{w})$。

namespace cjdst{
    const int N = 20, M = 400, L = 2000000, K = 26;
	int son[M + 5][K], fail[M + 5], cnt[M + 5];
	int dp[L + 5];
	std::string a[N + 5];
	int ctnode;
	int n, m;
	void insert(std::string &s){
		int cur = 0;
		for(char c:s){
			if(!son[cur][c - 'a']) son[cur][c - 'a'] = (++ctnode);
			cur = son[cur][c - 'a'];
		}
		cnt[cur] |= (1 << (s.size() - 1));
	}
	
	void build(){
		std::queue <int> q;
		for(int i = 0; i < K; i++){
			if(son[0][i]) q.push(son[0][i]);
		}
		while(!q.empty()){
			int head = q.front();
			q.pop();
			for(int i = 0; i < K; i++){
				if(!son[head][i]){
					son[head][i] = son[fail[head]][i];
				}else{
					fail[son[head][i]] = son[fail[head]][i];
					cnt[son[head][i]] |= cnt[fail[son[head][i]]];
					q.push(son[head][i]);
				}
			}
		}
	}
	
	void solve(){
		std::cin >> n >> m;
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
			insert(a[i]);
		}
		build();
		while(m--){
			std::string t;
			std::cin >> t;
			int cur = 0, ans = 0;
			unsigned dp = 1;
			for(int i = 0; i < t.size(); i++){
				cur = son[cur][t[i] - 'a'];
				if(cnt[cur] & dp){
					dp = dp << 1 | 1;
					ans = std::max(ans, i + 1);
				}else dp <<= 1;
			}
			std::cout << ans << '\n';
		}
	}
}

时间复杂度：$O(n|S||\Sigma|+m|T|)$。

ABC458F

这个在 https://www.acgo.cn/discuss/rest/77714 Week 7 最后一题口胡过了。

只不过当时我可能没意识到在建 fail 时已经可以预处理能不能到那个点了。

哦好像意识到了，但是反正复杂度瓶颈主要是 $O((n|S|)^3\log n)$，优不优化无所谓。

这是我今天写的第四个 AC 自动机，我感觉再写下去我得成写 AC 自动机 自动机了。

跑得还挺快的，只用了 86ms。

namespace cjdst{
    const ll N = 100, M = 26, mod = 998244353;
	int son[N + 5][M], fail[N + 5], cnt[N + 5];
	int ctnode;
	std::string a[N + 5];
	ll n, m;
	void insert(std::string &s){
		int cur = 0;
		for(char c:s){
			if(!son[cur][c - 'a']) son[cur][c - 'a'] = (++ctnode);
			cur = son[cur][c - 'a'];
		}
		cnt[cur] = 1;
	}
	void build(){
		std::queue <int> q;
		for(int i = 0; i < M; i++){
			if(son[0][i]) q.push(son[0][i]);
		}
		while(!q.empty()){
			int head = q.front();
			q.pop();
			for(int i = 0; i < M; i++){
				if(!son[head][i]) son[head][i] = son[fail[head]][i];
				else{
					fail[son[head][i]] = son[fail[head]][i];
					cnt[son[head][i]] |= cnt[fail[son[head][i]]];
					q.push(son[head][i]);
				}
			}
		}
	}
	
	struct Matrix{
		ll a[N + 5][N + 5];
		Matrix(){
			memset(a, 0, sizeof(a));
		}
		Matrix operator * (const Matrix &b) const{
			Matrix tmp;
			for(int i = 0; i <= ctnode; i++){
				for(int k = 0; k <= ctnode; k++){
					for(int j = 0; j <= ctnode; j++){
						tmp.a[i][j] += a[i][k] * b.a[k][j] % mod;
						tmp.a[i][j] %= mod;
					}
				}
			}
			return tmp;
		}
	};
	
	void solve(){
		std::cin >> m >> n;
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
			insert(a[i]);
		}
		build();
		Matrix mul, ans;
		ans.a[0][0] = 1;
		for(int i = 0; i <= ctnode; i++){
			for(int j = 0; j < M; j++){
				if(cnt[son[i][j]]) continue;
				mul.a[son[i][j]][i]++;
			}
		}
		while(m){
			if(m & 1) ans = mul * ans;
			mul = mul * mul, m >>= 1;
		}
		ll ans2 = 0;
		for(int i = 0; i <= ctnode; i++){
			ans2 += ans.a[i][0];
			ans2 %= mod;
		}
		std::cout << ans2 << '\n';
	}
}

时间复杂度：$O((n|S|)^3\log n)$。

P14363

Difficulty：4.5 / Easy

Tag：ACAM

三周目。真是一对苦命鸳鸯啊。

这就是让我挂 20pts 的下场。

记前缀、$S_1$ 中间、$S_2$ 中间、后缀分别为 $A,B,C,D$，则可以转化成 $A\{BC\{D$。

注意到一个文本串最多只能在模式串种被匹配一次。

所以直接求出 P5357 中 $\sum ans_i$ 即可。这个可以递推 $O(|T|)$ 求出。

namespace cjdst{
    const int N = 200000, M = 6000000, K = 27;
	int son[M + 5][K], fail[M + 5], cnt[M + 5];
	int ctnode;
	int n, m;
	void insert(std::string &s){
		int cur = 0;
		for(char c:s){
			if(!son[cur][c - 'a']) son[cur][c - 'a'] = (++ctnode);
			cur = son[cur][c - 'a'];
		}
		cnt[cur]++;
	}
	
	void build(){
		std::queue <int> q;
		for(int i = 0; i < K; i++){
			if(son[0][i]) q.push(son[0][i]);
		}
		while(!q.empty()){
			int head = q.front();
			q.pop();
			for(int i = 0; i < K; i++){
				if(!son[head][i]) son[head][i] = son[fail[head]][i];
				else{
					fail[son[head][i]] = son[fail[head]][i];
					cnt[son[head][i]] += cnt[fail[son[head][i]]];
					q.push(son[head][i]);
				}
			}
		}
	}
	
	int query(std::string &s){
		int cur = 0, ans = 0;
		for(char c:s){
			cur = son[cur][c - 'a'];
			ans += cnt[cur];
		}
		return ans;
	}
	
	void solve(){
		std::cin >> n >> m;
		for(int i = 1; i <= n; i++){
			std::string a, b, c;
			std::cin >> a >> b;
			if(a == b) continue;
			int l = 0, r = a.size();
			while(a[l] == b[l]) l++;
			while(a[r] == b[r]) r--;
			c = a.substr(0, l) + '{' + a.substr(l, r - l + 1) + b.substr(l, r - l + 1) + '{' + b.substr(r + 1, 10551480);
			insert(c);
		}
		build();
		while(m--){
			std::string a, b, c;
			std::cin >> a >> b;
			if(a.size() != b.size()){
				std::cout << "0\n";
				continue;
			}
			int l = 0, r = a.size();
			while(a[l] == b[l]) l++;
			while(a[r] == b[r]) r--;
			c = a.substr(0, l) + '{' + a.substr(l, r - l + 1) + b.substr(l, r - l + 1) + '{' + b.substr(r + 1, 10551480);
			std::cout << query(c) << '\n';
		}
	}
}

时间复杂度：$O(L_1|\Sigma|+L_2)$。

P2322

Difficulty：4.6 / Easy

Tag：ACAM

定义 $dis[cur][mask]$ 为当前匹配状态为 $cur$ 与总共匹配了串有 $mask$ 的最短距离，ACAM 套个广搜，最后反着找路径即可。

咦怎么还卡空间。

namespace cjdst{
    const int N = 12, M = 600, K = 26;
	int son[M + 5][K], fail[M + 5], cnt[M + 5];
	int ctnode;
	std::string a[N + 5];
	int dis[M + 5][1 << N];
	int lst1[M + 5][1 << N], lst2[M + 5][1 << N];
	char lst3[M + 5][1 << N];
	int n;
	void insert(int idx){
		int cur = 0;
		for(char c:a[idx]){
			if(!son[cur][c - 'A']) son[cur][c - 'A'] = (++ctnode);
			cur = son[cur][c - 'A'];
		}
		cnt[cur] |= (1 << idx - 1);
	}
	
	void build(){
		std::queue <int> q;
		for(int i = 0; i < K; i++){
			if(son[0][i]) q.push(son[0][i]);
		}
		while(!q.empty()){
			int head = q.front();
			q.pop();
			for(int i = 0; i < K; i++){
				if(!son[head][i]) son[head][i] = son[fail[head]][i];
				else{
					fail[son[head][i]] = son[fail[head]][i];
					cnt[son[head][i]] |= cnt[fail[son[head][i]]];
					q.push(son[head][i]);
				}
			}
		}
	}

	void solve(){
		std::cin >> n;
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
			insert(i);
		}
		build();
		std::queue <pii> q;
		memset(dis, 63, sizeof(dis));
		dis[0][0] = 0;
		q.push({0, 0});
		pii cur;
		while(!q.empty()){
			auto head = q.front();
			q.pop();
			if(head.second == (1 << n) - 1){
				cur = head;
				break;
			}
			for(int i = 0; i < K; i++){
				int x = son[head.first][i], y = head.second | cnt[son[head.first][i]];
				if(dis[x][y] == 0x3f3f3f3f){
					dis[x][y] = dis[head.first][head.second] + 1;
					lst1[x][y] = head.first;
					lst2[x][y] = head.second;
					lst3[x][y] = i + 'A';
					q.push({x, y});
				}
			}
		}
		std::string ans;
		while(cur.first || cur.second){
			int x = lst1[cur.first][cur.second], y = lst2[cur.first][cur.second];
			ans.push_back(lst3[cur.first][cur.second]);
			cur.first = x, cur.second = y;
		}
		std::reverse(ans.begin(), ans.end());
		std::cout << ans << '\n';
	}
}

时间复杂度：$O(2^n|S||\Sigma|)$。

空间复杂度：$O(2^n|S|)$。

后缀数组

显然 sort + 哈希二分比较大小可以做到 $O(n\log^2 n)$，但我现在才 16 岁，16 岁用双模哈希，32 岁就用四模哈希，64 岁就用八模哈希了，我不得成八常大数了？而且有 $O(n\log n)$ 做法我为啥不写/续标识

考虑倍增。我们通过每个位置后 $2^{i-1}$ 个字符的串的排名拼接得到 $2^i$ 个字符的排名，然后离散化一下。

如果直接 sort 的话还是 $O(n\log^2 n)$ 的，但是我们注意到每次倍增的值域只有 $n^2$，所以神秘两次基排就可以 $O(n\log n)$ 了。

这时你可能要问了，卧槽你这常数不得大飞啊。

没事，注意到我们在上一轮基排时其实已经求出了低位的排名了，所以通过上一次的排名，我们就可以将两次基排优化成 1.1 次基排。常数大大减小了（喜）

突然发现不会桶排，照着 OI-wiki 抄的，啥意思其实不知道（

namespace cjdst{
    const int N = 1000200, M = 128;
	int rnk[N + 5], oldrnk[N * 2 + 5], id[N + 5], sa[N + 5], bucket[N + 5];
	std::string a;
	int n;
	
	void solve2(int w){
		if(w >= n) return;
		int cur = 0;
		for(int i = n - w + 1; i <= n; i++){
			id[++cur] = i;
		}
		for(int i = 1; i <= n; i++){
			if(sa[i] > w) id[++cur] = sa[i] - w;
		}
		memset(bucket, 0, sizeof(bucket));
		for(int i = 1; i <= n; i++){
			bucket[rnk[i]]++;
		}
		for(int i = 1; i <= n + M; i++){
			bucket[i] += bucket[i - 1];
		}
		for(int i = n; i; i--){
			sa[bucket[rnk[id[i]]]--] = id[i];
		}
		for(int i = 1; i <= n; i++){
			oldrnk[i] = rnk[i];
		}
		
		int ctrnk = 0; 
		for(int i = 1; i <= n; i++){
			if(oldrnk[sa[i]] == oldrnk[sa[i - 1]] && oldrnk[sa[i] + w] == oldrnk[sa[i - 1] + w]){
				rnk[sa[i]] = ctrnk;
			}else{
				rnk[sa[i]] = (++ctrnk);
			}
		}
		solve2(w << 1);
	}
	
	void solve(){
		std::cin >> a;
		n = a.size();
		a = " " + a;
		for(int i = n; i; i--){
			rnk[i] = a[i];
			bucket[rnk[i]]++;
		}
		for(int i = 1; i <= M; i++){
			bucket[i] += bucket[i - 1];
		}
		for(int i = n; i; i--){
			sa[bucket[rnk[i]]--] = i;
		}
		for(int i = 1; i <= n; i++){
			oldrnk[i] = rnk[i];
		}
		solve2(1);
		for(int i = 1; i <= n; i++){
			std::cout << sa[i] << ' ';
		}
		std::cout << '\n';
	}
}

然后这玩意可以求一个叫做 height 的东西，定义如下：

$\text{height}(i)=\text{LCP}(A_{[\text{sa}_i,n]},A_{[\text{sa}_{i-1},n]})$。

这个有两个性质：

• $\text{height}(\text{rank}_i)\ge\text{height}(\text{rank}_{i-1})-1$
• $\text{LCP}(A_{[i,n]},A_{[j,n]})=\sum_{k=\text{rank}_i+1}^{\text{rank}_j}\text{height}(k)$

前者可以让你 $O(n)$ 递推求出 height，后者可以让你以 RMQ 的方式 $O(1)$ 计算一个串任意两个后缀最长公共前缀。

for(int i = 1; i <= n; i++){
	height[rank[i]] = std::max(0, height[rank[i - 1]] - 1);
	while(a[sa[rank[i]] + height[rank[i]]] == a[sa[rank[i] - 1] + height[rank[i]]]) height[rank[i]]++;
}

P3181

求公共子串个数。

$A=S_1+\{+S_2$，跑一遍 SA，然后转化成了求 $\sum_{i=1}^n\sum_{j=i+1}^n([\text{sa}_i\lt |S_1|+1]\oplus[\text{sa}_j\lt |S_1|+1])\min_{k=i+1}^j \text{height}(k)$。

那咋办？