P8085 [COCI2011-2012#4] KRIPTOGRAM 题解

本文原发布于2024-02-07洛谷题库 P8085 [COCI2011-2012#4] KRIPTOGRAM 题解区，现于2024-2-29转载至博客园

思路解析

这道题目的主要难点在于如何判断明文中形如 \(\texttt{a b c b}\) 的子串可以和密文 \(\texttt{b c a c}\) 匹配，因为如果单纯匹配字符的话将会无法匹配，所以我们需要找到一种新的储存一组明文和密文的方法。于是我们考虑存下上一个与当前字符串相同的字符串与当前字符串的距离，如果当前字符串在之前从来没出现过，就存下 \(0\)。这样下来我们就能正确的匹配明文和密文了。

接下来就要判断密文所对应的匹配数组是否在明文当中出现过，考虑使用滑动窗口做法。但由于删除子字符串会导致新的明文的匹配数组发生改变，所以我们需要同时存下来下一个与当前字符串相同的字符串的位置。原因是如果删掉一个明文的子字符串就会导致下一个与当前字符串相同的字符串的匹配数组的值变为 \(0\)。

最后我们就需要把已经求出来的两个匹配数组进行判断比较，但是如果对于每一个明文的子字符串都从头到尾比较一次的话时间复杂度就会达到 \(O((10^6)^2)\)，显然会 \(\text{TLE}\)，于是就要使用字符串哈希进行优化，如果没学过字符串哈希的可以去看这道题自学一下 P3370 【模板】字符串哈希。删除滑动窗口头部的元素相当于将哈希值减去元素的值 \(\times\) 它对应数位的权值，将滑动窗口右移则相当于将哈希值 \(\times BASE\)，添加尾部的新元素则是将哈希值直接加上元素的值，而对于元素的修改就是减去原来的，然后加上修改后的值。

code

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 1e6 + 10;
const ull P = 13331;
string a[N], b[N];
ull p[N], l1[N], l2[N], t1[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s1, s2;
	int n1 = 1, n2 = 1;
	cin >> s1;
	for(; s1 != "$"; n1++) {
		a[n1] = (s1);
		cin >> s1;
	}
	cin >> s2;
	for(; s2 != "$"; n2++) {
		b[n2] = (s2);
		cin >> s2;
	}
	n1--; n2--;
	p[0] = 1;
	for(int i = 1; i <= n1; i++) {
		p[i] = p[i - 1] * P;
	}
	map<string, int> mp1, mp2;
	ull h1 = 0, h2 = 0;
	for(int i = 1; i <= n2; i++) {
		if(mp1[a[i]] != 0) {
			l1[i] = i - mp1[a[i]];
			t1[mp1[a[i]]] = i;
		}
		else l1[i] = 0;
		mp1[a[i]] = i;
		h1 = h1 * P + l1[i];

		if(mp2[b[i]] != 0) {
			l2[i] = i - mp2[b[i]];
		}
		else l2[i] = 0;
		mp2[b[i]] = i;
		h2 = h2 * P + l2[i];
	}
	if(h1 == h2) {
		cout << 1;
		return 0;
	}
	for(int i = 2; i + n2 - 1 <= n1; i++) {
		int r = i + n2 - 1;
		h1 = (h1 - l1[i - 1] * p[n2 - 1]) * P;
		if(mp1[a[i - 1]] == i - 1) {
			mp1[a[i - 1]] = 0;
		}
		if(t1[i - 1] != 0) {
			h1 -= l1[t1[i - 1]] * p[r - t1[i - 1]];
			l1[t1[i - 1]] = 0;
		}
		if(mp1[a[r]] != 0) {
			l1[r] = r - mp1[a[r]];
			t1[mp1[a[r]]] = r;
		} 
		else l1[r] = 0;
		mp1[a[r]] = r;
		h1 += l1[r];
		if(h1 == h2) {
			cout << i;
			return 0;
		}
	}
	return 0;
}