Sequence I
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1013 Accepted Submission(s): 393
Problem Description
Mr. Frog has two sequences a1,a2,⋯,an
and b1,b2,⋯,bm
and a number p. He wants to know the number of positions q such that sequence b1,b2,⋯,bm
is exactly the sequence aq,aq+p,aq+2p,⋯,aq+(m−1)p
where q+(m−1)p≤n
and q≥1
.
Input
The first line contains only one integer T≤100
, which indicates the number of test cases.
Each test case contains three lines.
The first line contains three space-separated integers 1≤n≤106,1≤m≤106
and 1≤p≤106
.
The second line contains n integers a1,a2,⋯,an(1≤ai≤109)
.
the third line contains m integers b1,b2,⋯,bm(1≤bi≤109)
.
Output
For each test case, output one line “Case #x: y”, where x is the case number (starting from 1) and y is the number of valid q’s.
Sample Input
2
6 3 1
1 2 3 1 2 3
1 2 3
6 3 2
1 3 2 2 3 1
1 2 3
Sample Output
Case #1: 2
Case #2: 1
Source
题意：
题解：
kmp
/******************************
code by drizzle
blog: www.cnblogs.com/hsd-/
^ ^ ^ ^
O O
******************************/
#include<bits/stdc++.h>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<vector>
#include<string>
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define A first
#define B second
const int mod=;
const int MOD1=;
const int MOD2=;
const double EPS=0.00000001;
//typedef long long ll;
typedef __int64 ll;
const ll MOD=;
const int INF=;
const ll MAX=1ll<<;
const double eps=1e-;
const double inf=~0u>>;
const double pi=acos(-1.0);
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
int f[];
void get(int *p,int m)
{
int j=;
f[]=f[]=;
for(int i=;i<m;i++)
{
j=f[i];
while(j&&p[j]!=p[i]) j=f[j];
if(p[i]==p[j]) f[i+]=j+;
else f[i+]=;
}
}
int kmp(int *s,int *p,int n,int m)
{
int num=;
int j=;
for(int i=;i<n;i++)
{
while(j&&p[j]!=s[i]) j=f[j];
if(s[i]==p[j]) j++;
if(j==m) num++;
}
return num;
}
int s[],p[],t[];
int n,m,q;
int main()
{
int T;
scanf("%d",&T);
for(int k=;k<=T;k++)
{
scanf("%d %d %d",&n,&m,&q);
memset(t,,sizeof(t));
memset(p,,sizeof(p));
for(int i=;i<n;i++)
scanf("%d",&t[i]);
for(int i=;i<m;i++)
scanf("%d",&p[i]);
get(p,m);
int ans=;
for(int i=;i<q;i++)
{
int num=;
for(int j=i;j<n&&i+(m-)*q<n;j+=q)
s[num++]=t[j];
ans+=kmp(s,p,num,m);
}
printf("Case #%d: %d\n",k,ans);
}
return ;
}
/*
KMP 处理
*
模拟
/******************************
code by drizzle
blog: www.cnblogs.com/hsd-/
^ ^ ^ ^
O O
******************************/
#include<bits/stdc++.h>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<vector>
#include<string>
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define A first
#define B second
const int mod=;
const int MOD1=;
const int MOD2=;
const double EPS=0.00000001;
//typedef long long ll;
typedef __int64 ll;
const ll MOD=;
const int INF=;
const ll MAX=1ll<<;
const double eps=1e-;
const double inf=~0u>>;
const double pi=acos(-1.0);
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
int t;
int a[];
int b[];
int d[];
map<int,int> mp;
vector<int > ve[];
int n,m,p;
int main()
{
while(scanf("%d",&t)!=EOF)
{
for(int l=; l<=t; l++)
{
mp.clear();
scanf("%d %d %d",&n,&m,&p);
for(int i=; i<=n; i++)
scanf("%d",&a[i]);
int jishu=;
for(int i=; i<=m; i++ )
{
ve[i].clear();
scanf("%d",&b[i]);
if(mp[b[i]]==)
{
mp[b[i]]=jishu;
d[jishu]=i;
jishu++;
}
}
int minx=;
int what=;
for(int i=; i<=n; i++)
{
if(mp[a[i]])
{
ve[mp[a[i]]].push_back(i);
}
}
for(int i=; i<jishu; i++)
{
if(minx>ve[i].size())
{
minx=ve[i].size();
what=i;
}
}
int sum=;
for(int i=; i<ve[what].size(); i++)
{
int st=ve[what][i]-(d[mp[a[ve[what][i]]]]-)*p;
int ed=ve[what][i]+(m-d[mp[a[ve[what][i]]]])*p;
int zha=;
int flag=;
if(st<||ed>n)
flag=;
if(flag==)
{
for(int j=st; j<=ed; j+=p)
{
if(a[j]!=b[zha++])
{
flag=;
break;
}
}
}
if(flag==)
sum++;
}
printf("Case #%d: %d\n",l,sum);
}
}
return ;
}