Codeforces Round〹344(Div.2)D.Messenger kmp

D.Messenger
テーマ接続:
http://www.codeforces.com/contest/631/problem/D
Description
Each employee of the「Blake Techologies」company uses a special messaging ap「Blake Messenger」.All the stuff likes this ap and uses it constantly.However，some portent futures are.Foxample。many users want to be able to search through the message history.It was already announced that the new feature will appar in the neart udate，when developers faced some trours throuble.ore.com.ore.ore.ore.ore.ory.ory.ort.ory.ory.ory.ore.ort.ort.ory.ory.ory.aute。
All the messages are represented as.streings consisting of only lowercase English letters.In order to reduce the network load streings are represented in the special compreed form.Compreession algorithm works stars.Comporation。each block containing only equal characters.One block may be described a s a pair(li、_;ci)、where lis the length of the i-th block and ci is the cores ponding pointing.Thus、the string mattery
Your t ask is to write the program、that given twocopresed stint and s finds s finds all crcrences of s.Developers know that there may be may such ch crences、so they onlyask to find thenumbebest thethethethe aatttttttttttttttttthethethethethethe thethethethethethethethethethethethe attmmmmmmmmmmmmthethethethethethethethethethethethethethethethetheaaatttttthththththththththththththththththththththth1…t p̵＋̵̵s-𔎅1𔎅=𔎅s，where ti is the i-th character of string t.
Note that the way to represent the streing in copresed form may not be unique.For example string“aa”may be given as，…
Input
The first line of the input contains two integers n and m(1̵≦𔎅n，𔎅m≦𔎅200𔎅000)-the number of blocks in strigs and s，s，respively.
The second line contains the descriptions of n parts of string t in the format「li-ci」（1_;≦𔎅li̵1≦𔎅1000)—the length of the i-th parth and the coress.Enterporese.End。
The second line contains the descriptions of m part s of string s in the format「li-ci」（1_;≦𔎅li̵1≦𔎅1000)—the length of the i-th parth and the coress.End loress.
Output
Print a single integer-the number of occurrences of s in t.
Sample Input
5 3-a 2-b 4-c 3-a 2-c 2-a 2-b 1-c
Sample Output
1
ベント
題意
二文字列をあげます。
各文字列があなたにあげる形式は、l 1つのc 1があります。最初の位置にl 2つのc 2があります。このように。
そして、最初の文字列のうち、いくつかと第二の文字列と同じ部分列がありますか？
クイズ:
KMPでいいです
これとkmpは同じです。唯一の違いは開始位置と終了位置の間で、この二つの位置のマッチングは最初の列とこの二つの位置の文字が第二の列の文字より大きいだけでいいです。
注意隣の文字は同じかもしれません。
8 5−a 1−b 1−c 1−a 2−b 1−c 1−a 1−b 1−a 1−b 1−b 1−c 1−a 1−b 1−a 1−b 1−b
この場合、通常のkmpのようにp[j]に跳ね返すことができません。
そこで私たちは暴力的に直接0に飛び込めばいいです。
コード

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+4;
vector<pair<long long,int> >V1,V2;
int n,m;
int p[maxn];
void kmp()
{
    int j=0;
    for(int i=1;i<V2.size();i++)
    {
        j=p[i];
        while(j&&V2[j]!=V2[i])j=p[j];
        if(V2[j]==V2[i])p[i+1]=j+1;
    }
}
void get()
{
    int j=0;
    long long ans = 0;
    for(int i=0;i<V1.size();i++)
    {
        if(j==V2.size()-1&&V2[j].second==V1[i].second&&V2[j].first<=V1[i].first)j++;
        else{
            while(j&&V2[j]!=V1[i])j=p[j];
            if(j==0&&V2[j].second==V1[i].second&&V2[j].first<=V1[i].first)j++;
            else if(V2[j]==V1[i])j++;
        }
        if(j==V2.size())
        {
            if(V1[i].first>V2[j-1].first)
                ans++,j=0,i--;
            else
                ans++,j=p[j];
        }
    }
    printf("%lld
",ans);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        long long x;char y;
        scanf("%lld",&x);
        scanf("%c",&y);
        scanf("%c",&y);
        int z=y-'a'+1;
        if(V1.size()&&V1.back().second==z)
            V1.back().first+=x;
        else
            V1.push_back(make_pair(x,z));
    }
    for(int i=1;i<=m;i++)
    {
        long long x;char y;
        scanf("%lld",&x);
        scanf("%c",&y);
        scanf("%c",&y);
        int z=y-'a'+1;
        if(V2.size()&&V2.back().second==z)
            V2.back().first+=x;
        else
            V2.push_back(make_pair(x,z));
    }
    if(V2.size()==1)
    {
        long long ans = 0;
        for(int i=0;i<V1.size();i++)
            if(V1[i].second==V2[0].second&&V1[i].first>=V2[0].first)
                ans+=(V1[i].first-V2[0].first+1);
        printf("%lld
",ans);
        return 0;
    }
    kmp();
    get();
    return 0;
}