CF631D Messenger （kmp + 字符串处理）

CF631D Messenger

kmp + 字符串处理

思路简单，写起来细节比较多

首先要合并同类项，然后再考虑什么时候 \(s=t\)。如果合并后 \(t\) 有一种或两种字符，那么都可以直接做；大于两种，我们发现匹配的条件为：中间部分完全相同，首尾字符相同并且 \(s\) 首尾字符的数量要大于 \(t\)。

中间部分完全相同等价于字符和出现次数完全相同，所以我们只需要将这两个东西体现在字符串中，然后中间部分做 kmp 匹配，每当匹配到以后，判断两边是否满足条件即可。

复杂度 \(O(n)\)。我的实现不好，所以代码量又大，看上去又丑。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 1800010;
int n, m;
i64 ans;
i64 pretot, suftot;
char pre, suf, k;
std::string s, t;
i64 tot[N], id[N], nxt[N];
char c[200010];
char d[N];
int num;
int main() {
	std::cin >> n >> m;

	i64 lst = -1, lsttot = 0;
	for(int i = 1; i <= n; i++) {
		char a, b;
		std::cin >> tot[i] >> b >> a;

		if(lst == -1) lst = a, lsttot = tot[i];
		else if(lst == a) {
			lsttot += tot[i];
		} else {
			s += lst;
			char x[20];
			sprintf(x, "%lld", lsttot);
			s += x;
			c[++num] = lst;
			tot[num] = lsttot;
			lsttot = tot[i];
			lst = a;
		}
	}
	if(lst != -1) {
		s += lst;
		char x[12];
		
		sprintf(x, "%lld", lsttot);
		s += x;
		c[++num] = lst;
		tot[num] = lsttot;
	} //合并同类项
    
	s = "#" + s;
	int nw = 1, slen = s.length() - 1;
	for(int i = 1; i <= num; i++) {
		int j = nw;
		for(; j <= slen; j++) {
			if(s[j] >= 'a' && s[j] <= 'z' && s[nw] != s[j]) break;
			id[j] = i; 
			d[j] = c[i];
		}
		nw = j;
	}
    
	int flg = 0;
	lst = -1, lsttot = 0;
	for(int i = 1; i <= m; i++) {
		char a, b;
		int v;
		std::cin >> v >> b >> a;

		if(lst == -1) lst = a, lsttot = v;
		else if(lst == a) {
			lsttot += v;
		} else {
			if(!flg) pre = lst, pretot = lsttot, flg++, lst = a, lsttot = v;
			else {
				t += lst;
				char x[20];
				sprintf(x, "%lld", lsttot);
				t += x;
				lsttot = v;
				lst = a;
				flg++;
			}
		}
	}
	if(lst != -1) {
		suf = lst, suftot = lsttot;
		flg++;
	} //合并同类项
	t = "#" + t;
    
	if(flg == 1) {
		pre = (pre | suf), pretot = (pretot | suftot);
		for(int i = 1; i <= num; i++) {
			if(c[i] == pre && tot[i] >= pretot) ans += 1LL * (tot[i] - pretot + 1);
		}
		std::cout << ans << "\n";
		return 0;
	} else if(flg == 2) {
		for(int i = 1; i < num; i++) {
			if(c[i] == pre && tot[i] >= pretot && c[i + 1] == suf && tot[i + 1] >= suftot) ans++;
		}
		
		std::cout << ans << "\n";
		return 0;
	} //特判

	int tlen = t.length() - 1;
	for(int i = 2, j = 0; i <= tlen; i++) {
		while(j && t[i] != t[j + 1]) j = nxt[j];
		if(t[i] == t[j + 1]) j++;
		nxt[i] = j;
	}
	for(int i = 1, j = 0; i <= slen; i++) {
		while(j && s[i] != t[j + 1]) j = nxt[j];
		if(s[i] == t[j + 1]) j++;
		if(j == tlen) {
			if(tot[id[i + 1]] >= suftot && d[i + 1] == suf) {
				if(tot[id[i - tlen]] >= pretot && d[i - tlen] == pre) ans++;
			} 
		} 
	} //普通情况

	std::cout << ans << "\n";

	return 0;
}