Java(javac 1.8) 解法, 执行用时: 393ms, 内存消耗: 42952K, 提交时间: 2019-12-07 23:44:43
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) throws IOException {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader sc = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task solver = new Task();
solver.solve(1, sc, out);
out.close();
}
static class Task {
public int[] getNext(Node[] p,int len) {
int[] next=new int[len+10];
int i=0;
int j=-1;
next[i]=-1;
while(i<len) { //构造next数组
if(j==-1||(p[i].c==p[j].c&&p[i].cnt==p[j].cnt))
next[++i]=++j;
else
j=next[j];
}
return next;
}
public long KMP(Node[] x,int m,Node[] y,int n,Node[] nowS,int cntS) { //x是模式串 y是主串
int i,j;
long ans=0;
i=j=0;
int[] next=getNext(x,m);
while(i<n){
while(j!=-1 && (y[i].c!=x[j].c||y[i].cnt!=x[j].cnt))
j=next[j];
i++;
j++;
if(j>=m){
int index=i-m-1;
if(index>=0&&i<n) {
if(y[index].c==nowS[0].c&&y[index].cnt>=nowS[0].cnt&&y[i].c==nowS[cntS-1].c&&y[i].cnt>=nowS[cntS-1].cnt)
ans++;
}
j=next[j];
}
}
return ans;
}
public void solve(int testNumber, InputReader sx, PrintWriter outs) throws IOException {
/* File file_in=new File("C:\\Users\\Garett\\Desktop\\题目\\String Compression\\数据","16.in");
FileReader in=new FileReader(file_in);
BufferedReader sc=new BufferedReader(in);
File file_out=new File("C:\\Users\\Garett\\Desktop\\题目\\String Compression\\数据","16.out");
FileWriter out=new FileWriter(file_out);
BufferedWriter puts=new BufferedWriter(out);
String[] temp=sc.readLine().split(" ");
int n=Integer.parseInt(temp[0]);
int m=Integer.parseInt(temp[1]);*/
int n=sx.nextInt();
int m=sx.nextInt();
Node[] t=new Node[n];
Node[] s=new Node[m];
int cnt=0;
/* temp=sc.readLine().split(" ");
for(int i=0;i<2*n;i+=2) {
long l=Long.parseLong(temp[i]);
char c=temp[i+1].charAt(0);
// System.out.println(l+" "+c);
t[cnt++]=new Node(c,l);
}
cnt=0;
// System.out.println();
temp=sc.readLine().split(" ");
for(int i=0;i<2*m;i+=2) {
long l=Long.parseLong(temp[i]);
char c=temp[i+1].charAt(0);
//System.out.println(l+" "+c);
s[cnt++]=new Node(c,l);
}*/
for(int i=0;i<n;i++) {
long l=sx.nextLong();
char c=sx.next().charAt(0);
// System.out.println(l+" "+c);
t[cnt++]=new Node(c,l);
}
cnt=0;
// System.out.println();
// temp=sc.readLine().split(" ");
for(int i=0;i<m;i++) {
long l=sx.nextLong();
char c=sx.next().charAt(0);
//System.out.println(l+" "+c);
s[cnt++]=new Node(c,l);
}
Node[] nowT=new Node[n];
Node[] nowS=new Node[m];
int cntT=0;
int cntS=0;
nowT[cntT++]=t[0];
nowS[cntS++]=s[0];
for(int i=1;i<n;i++) {
if(t[i].c==nowT[cntT-1].c)
nowT[cntT-1].cnt+=t[i].cnt;
else
nowT[cntT++]=t[i];
}
for(int i=1;i<m;i++) {
if(s[i].c==nowS[cntS-1].c)
nowS[cntS-1].cnt+=s[i].cnt;
else
nowS[cntS++]=s[i];
}
if(cntS==1) {
long ans=0;
for(int i=0;i<cntT;i++) {
if(nowT[i].c==nowS[0].c&&nowT[i].cnt>=nowS[0].cnt) {
ans+=nowT[i].cnt-nowS[0].cnt+1;
}
}
/* puts.write(ans+"");
puts.newLine();
puts.close();
sc.close();*/
outs.println(ans);
return ;
}
if(cntS==2) {
long ans=0;
for(int i=0;i<cntT-1;i++) {
if(nowT[i].c==nowS[0].c&&nowT[i+1].c==nowS[1].c&&nowT[i].cnt>=nowS[0].cnt&&nowT[i+1].cnt>=nowS[1].cnt)
ans++;
}
outs.println(ans);
/* puts.write(ans+"");
puts.newLine();
puts.close();
sc.close();*/
return ;
}
Node[] bufS=new Node[cntS];
int nowCntS=0;
for(int i=1;i<cntS-1;i++)
bufS[nowCntS++]=nowS[i];
outs.println(KMP(bufS,nowCntS,nowT,cntT,nowS,cntS));
/* puts.write(KMP(bufS,nowCntS,nowT,cntT,nowS,cntS)+"");
puts.newLine();
puts.close();
sc.close();*/
}
}
static class Node{
char c;
long cnt;
public Node(char c,long cnt) {
this.c=c;
this.cnt=cnt;
}
}
static class InputReader{
StreamTokenizer tokenizer;
public InputReader(InputStream stream){
tokenizer=new StreamTokenizer(new BufferedReader(new InputStreamReader(stream)));
tokenizer.ordinaryChars(33,126);
tokenizer.wordChars(33,126);
}
public String next() throws IOException {
tokenizer.nextToken();
return tokenizer.sval;
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public boolean hasNext() throws IOException {
int res=tokenizer.nextToken();
tokenizer.pushBack();
return res!=tokenizer.TT_EOF;
}
public double nextDouble() throws NumberFormatException, IOException {
return Double.parseDouble(next());
}
public BigInteger nextBigInteger() throws IOException {
return new BigInteger(next());
}
}
}
C++11(clang++ 3.9) 解法, 执行用时: 64ms, 内存消耗: 10296K, 提交时间: 2019-12-07 23:46:10
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6+7;
struct node{
ll x;
char val;
};
vector<node> s,t;
ll nextt[N],extend[N];
void getnext(vector<node> s){
ll po; ll len=s.size();
nextt[0]=len;
ll pos=0;
while(pos<len-1&&s[pos].x==s[pos+1].x&&s[pos].val==s[pos].val) pos++;
nextt[1]=pos;
po=1;
for(ll i=2;i<len;i++){
if(nextt[i-po]+i<po+nextt[po])
nextt[i]=nextt[i-po];
else{
ll j=po+nextt[po]-i;
if(j<0) j=0;
while(i+j<len&&s[j].x==s[i+j].x&&s[j].val==s[i+j].val) j++;
nextt[i]=j;
po=i;
}
}
}
void exkmp(vector<node> a,vector<node> b){
ll len1=a.size(); ll len2=b.size();
getnext(a);
ll po; ll pos=0;
while(pos<len1&&pos<len2&&a[pos].x==b[pos].x&&a[pos].val==b[pos].val) pos++;
extend[0]=pos;
po=0;
for(ll i=1;i<len2;i++){
if(nextt[i-po]+i<extend[po]+po)
extend[i]=nextt[i-po];
else{
ll j=po+extend[po]-i;
if(j<0) j=0;
while(i+j<len2&&j<len1&&a[j].x==b[i+j].x&&a[j].val==b[i+j].val) j++;
extend[i]=j;
po=i;
}
}
}
int main(){
ll n,m; scanf("%lld%lld",&n,&m);
ll lastx=0; char lastc=' ';
for(ll i=1;i<=n;i++){
ll x; char va;
scanf("%lld %c",&x,&va);
if(va==lastc) s[(ll)(s.size()-1)].x+=x;
else s.push_back(node{x,va});
lastc=va;
}
lastx=0; lastc=' ';
for(ll i=1;i<=m;i++){
ll x; char va;
scanf("%lld %c",&x,&va);
if(va==lastc) t[(ll)(t.size()-1)].x+=x;
else t.push_back(node{x,va});
lastc=va;
}
ll ans=0;
if(t.size()==1){
for(ll i=0;i<s.size();i++){
if(s[i].val==t[0].val)
ans+=max(0ll,s[i].x-t[0].x+1);
}
printf("%lld\n",ans);
return 0;
}
vector<node> tmp;
for(ll i=0;i<t.size();i++){
if(i==0||i==t.size()-1) continue;
tmp.push_back(t[i]);
}
exkmp(tmp,s);
ll len=s.size(),val=tmp.size();
for(ll i=1;i<len;i++){
if(extend[i]==val&&t[0].x<=s[i-1].x&&t[0].val==s[i-1].val&&t[(ll)(t.size()-1)].x<=s[i+extend[i]].x
&&t[(ll)(t.size()-1)].val==s[i+extend[i]].val) ans++;
}
printf("%lld\n",ans);
}
,
,c为小写拉丁字母。