codeforces 631D. Messenger kmp

题目链接

首先想到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-8;
const int mod = 1e9+7;
const int inf = 1061109567;
const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
const int maxn = 2e5+5;
pair <ll, char> a[maxn], b[maxn];
#define next nextt
int n, m, next[maxn];
void init_kmp() {
    int i = 0, j = -1;
    next[0] = -1;
    while(i<m) {
        if(j == -1 || 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 = 0; i<n; i++) {
        scanf("%I64d-%c", &x, &ch);
        a[i] = mk(x, ch);
    }
    for(int i = 0; i<m; i++) {
        scanf("%I64d-%c", &x, &ch);
        b[i] = mk(x, ch);
    }
    int cnt = 0;
    for(int i = 0; i<n-1; i++) {
        if(a[i].se == a[i+1].se) {
            a[cnt].fi += a[i+1].fi;
            continue;
        }
        a[++cnt] = a[i+1];
    }
    n = cnt+1;
    cnt = 0;
    for(int i = 0; i<m-1; i++) {
        if(b[i].se == b[i+1].se) {
            b[cnt].fi += b[i+1].fi;
            continue;
        }
        b[++cnt] = b[i+1];
    }
    m = cnt+1;
    ll ans = 0;
    if(m == 1) {
        for(int i = 0; i<n; i++) {
            if(a[i].se == b[0].se&&a[i].fi>=b[0].fi) {
                ans += (a[i].fi-b[0].fi+1);
            }
        }
        cout<<ans<<endl;
        return 0;
    }
    if(m == 2) {
        for(int i = 0; i<n-1; i++) {
            if(a[i].se == b[0].se && a[i+1].se == b[1].se && a[i].fi>=b[0].fi&&a[i+1].fi>=b[1].fi) {
                ans ++;
            }
        }
        cout<<ans<<endl;
        return 0;
    }
    pair <ll, char> s, e;
    s = b[0], e = b[m-1];
    cnt = 0;
    for(int i = 1; i<m-1; i++) {
        b[cnt++] = b[i];           //去掉头尾
    }
    m -= 2;
    init_kmp();
    int i = 1, j = 0;
    while(i<n-1) {
        if(j == -1 || a[i] == b[j]) {
            i++, j++;
        } else {
            j = next[j];
        }
        if(j == m) {
            if(s.se == a[i-j-1].se && s.fi<=a[i-j-1].fi
               && a[i].se == e.se && a[i].fi>=e.fi) {
                    ans++;
            }
            j = next[j];
        }
    }
    cout<<ans<<endl;
    return 0;
}