题目链接

首先想到kmp, 和普通的不一样的是,中间部分严格相等, 头和尾的字符相等但是数量可以不相等。 所以应该把子串的头和尾先去掉,然后对剩下的部分进行kmp。

子串长度为1或2要特别讨论。

不要忘记一开始先把相邻的相同的部分合并掉。

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
const int maxn = 2e5+;
pair <ll, char> a[maxn], b[maxn];
#define next nextt
int n, m, next[maxn];
void init_kmp() {
int i = , j = -;
next[] = -;
while(i<m) {
if(j == - || b[i] == b[j]) {
++i, ++j;
next[i] = j;
} else {
j = next[j];
}
}
}
int main()
{
int x;
char ch;
cin>>n>>m;
for(int i = ; i<n; i++) {
scanf("%I64d-%c", &x, &ch);
a[i] = mk(x, ch);
}
for(int i = ; i<m; i++) {
scanf("%I64d-%c", &x, &ch);
b[i] = mk(x, ch);
}
int cnt = ;
for(int i = ; i<n-; i++) {
if(a[i].se == a[i+].se) {
a[cnt].fi += a[i+].fi;
continue;
}
a[++cnt] = a[i+];
}
n = cnt+;
cnt = ;
for(int i = ; i<m-; i++) {
if(b[i].se == b[i+].se) {
b[cnt].fi += b[i+].fi;
continue;
}
b[++cnt] = b[i+];
}
m = cnt+;
ll ans = ;
if(m == ) {
for(int i = ; i<n; i++) {
if(a[i].se == b[].se&&a[i].fi>=b[].fi) {
ans += (a[i].fi-b[].fi+);
}
}
cout<<ans<<endl;
return ;
}
if(m == ) {
for(int i = ; i<n-; i++) {
if(a[i].se == b[].se && a[i+].se == b[].se && a[i].fi>=b[].fi&&a[i+].fi>=b[].fi) {
ans ++;
}
}
cout<<ans<<endl;
return ;
}
pair <ll, char> s, e;
s = b[], e = b[m-];
cnt = ;
for(int i = ; i<m-; i++) {
b[cnt++] = b[i]; //去掉头尾
}
m -= ;
init_kmp();
int i = , j = ;
while(i<n-) {
if(j == - || a[i] == b[j]) {
i++, j++;
} else {
j = next[j];
}
if(j == m) {
if(s.se == a[i-j-].se && s.fi<=a[i-j-].fi
&& a[i].se == e.se && a[i].fi>=e.fi) {
ans++;
}
j = next[j];
}
}
cout<<ans<<endl;
return ;
}

最新文章

  1. CentOS7之按时间段截取指定的Tomcat日志到指定文件的方法
  2. Atitit prj 项目管理与行政管理(1)------项目环境的概览与建立
  3. lightoj 1074 spfa判断负环
  4. Set up your first C# test with NUnit or resharper
  5. 论i++与++i
  6. eclipse搭建Log4J日志环境
  7. C# XML与Json之间相互转换
  8. 普通内存、ECC内存和REG ECC内存有什么不同
  9. 关于npm安装报错 网络问题等等等
  10. Docker-Compose入门
  11. [转]Jmeter + Grafana + InfluxDB 性能测试监控
  12. Yii2总结
  13. Nginx+Keepalived部署
  14. nullptr/NULL
  15. 连续三月涨势明显,PostgreSQL 将崛起?
  16. pdf.js 的使用
  17. js 创建对象的几种方法
  18. c算法
  19. 数据挖掘Apriori算法——学习笔记
  20. Jquery 事件执行两次

热门文章

  1. JS禁止/启用滚动条
  2. mac nodejs&amp;npm 安装
  3. ORA-01157报错&quot;cannot identify/lock data file&quot;解决
  4. linux查看端口占用
  5. JavaWeb核心编程之(三.4)Servlet Context 配置
  6. MyIsam与InnoDB主要区别
  7. MySQLdb autocommit
  8. 判断进程是64bit还是32bit
  9. Protection 5 ---- Priviliege Level Checking 2
  10. 常用Vxworks编程API