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

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

2016中国大学生程序设计竞赛（长春）-重现赛

题意：

题解：

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 ;

 }

巴特西

HDU 5918 KMP/模拟

Sequence I

最新文章

热门文章