首页 > 代码库 > HDU 5918 KMP/模拟
HDU 5918 KMP/模拟
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).
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
2016中国大学生程序设计竞赛（长春）-重现赛
题意：
题解：
kmp
1 /****************************** 2 code by drizzle 3 blog: www.cnblogs.com/hsd-/ 4 ^ ^ ^ ^ 5 O O 6 ******************************/ 7 #include<bits/stdc++.h> 8 #include<map> 9 #include<set>10 #include<cmath>11 #include<queue>12 #include<bitset>13 #include<math.h>14 #include<vector>15 #include<string>16 #include<stdio.h>17 #include<cstring>18 #include<iostream>19 #include<algorithm>20 #pragma comment(linker, "/STACK:102400000,102400000")21 using namespace std;22 #define A first23 #define B second24 const int mod=1000000007;25 const int MOD1=1000000007;26 const int MOD2=1000000009;27 const double EPS=0.00000001;28 //typedef long long ll;29 typedef __int64 ll;30 const ll MOD=1000000007;31 const int INF=1000000010;32 const ll MAX=1ll<<55;33 const double eps=1e-5;34 const double inf=~0u>>1;35 const double pi=acos(-1.0);36 typedef double db;37 typedef unsigned int uint;38 typedef unsigned long long ull;39 int f[2000100];40 void get(int *p,int m)41 {42 int j=0;43 f[0]=f[1]=0;44 for(int i=1;i<m;i++)45 {46 j=f[i];47 while(j&&p[j]!=p[i]) j=f[j];48 if(p[i]==p[j]) f[i+1]=j+1;49 else f[i+1]=0;50 }51 }52 int kmp(int *s,int *p,int n,int m)53 {54 int num=0;55 int j=0;56 for(int i=0;i<n;i++)57 {58 while(j&&p[j]!=s[i]) j=f[j];59 if(s[i]==p[j]) j++;60 if(j==m) num++;61 }62 return num;63 }64 int s[2000100],p[2000100],t[2000100];65 int n,m,q;66 int main()67 {68 int T;69 scanf("%d",&T);70 for(int k=1;k<=T;k++)71 {72 scanf("%d %d %d",&n,&m,&q);73 memset(t,0,sizeof(t));74 memset(p,0,sizeof(p));75 for(int i=0;i<n;i++)76 scanf("%d",&t[i]);77 for(int i=0;i<m;i++)78 scanf("%d",&p[i]);79 get(p,m);80 int ans=0;81 for(int i=0;i<q;i++)82 {83 int num=0;84 for(int j=i;j<n&&i+(m-1)*q<n;j+=q)85 s[num++]=t[j];86 ans+=kmp(s,p,num,m);87 }88 printf("Case #%d: %d\n",k,ans);89 }90 return 0;91 }92 /*93 KMP 处理94 *
模拟
1 /****************************** 2 code by drizzle 3 blog: www.cnblogs.com/hsd-/ 4 ^ ^ ^ ^ 5 O O 6 ******************************/ 7 #include<bits/stdc++.h> 8 #include<map> 9 #include<set> 10 #include<cmath> 11 #include<queue> 12 #include<bitset> 13 #include<math.h> 14 #include<vector> 15 #include<string> 16 #include<stdio.h> 17 #include<cstring> 18 #include<iostream> 19 #include<algorithm> 20 #pragma comment(linker, "/STACK:102400000,102400000") 21 using namespace std; 22 #define A first 23 #define B second 24 const int mod=1000000007; 25 const int MOD1=1000000007; 26 const int MOD2=1000000009; 27 const double EPS=0.00000001; 28 //typedef long long ll; 29 typedef __int64 ll; 30 const ll MOD=1000000007; 31 const int INF=1000000010; 32 const ll MAX=1ll<<55; 33 const double eps=1e-5; 34 const double inf=~0u>>1; 35 const double pi=acos(-1.0); 36 typedef double db; 37 typedef unsigned int uint; 38 typedef unsigned long long ull; 39 int t; 40 int a[1000006]; 41 int b[1000006]; 42 int d[1000006]; 43 map<int,int> mp; 44 vector<int > ve[1000006]; 45 int n,m,p; 46 int main() 47 { 48 while(scanf("%d",&t)!=EOF) 49 { 50 for(int l=1; l<=t; l++) 51 { 52 mp.clear(); 53 scanf("%d %d %d",&n,&m,&p); 54 for(int i=1; i<=n; i++) 55 scanf("%d",&a[i]); 56 int jishu=1; 57 for(int i=1; i<=m; i++ ) 58 { 59 ve[i].clear(); 60 scanf("%d",&b[i]); 61 if(mp[b[i]]==0) 62 { 63 mp[b[i]]=jishu; 64 d[jishu]=i; 65 jishu++; 66 } 67 } 68 int minx=10000000; 69 int what=0; 70 for(int i=1; i<=n; i++) 71 { 72 if(mp[a[i]]) 73 { 74 ve[mp[a[i]]].push_back(i); 75 } 76 } 77 for(int i=1; i<jishu; i++) 78 { 79 if(minx>ve[i].size()) 80 { 81 minx=ve[i].size(); 82 what=i; 83 } 84 } 85 int sum=0; 86 for(int i=0; i<ve[what].size(); i++) 87 { 88 int st=ve[what][i]-(d[mp[a[ve[what][i]]]]-1)*p; 89 int ed=ve[what][i]+(m-d[mp[a[ve[what][i]]]])*p; 90 int zha=1; 91 int flag=0; 92 if(st<1||ed>n) 93 flag=1; 94 if(flag==0) 95 { 96 for(int j=st; j<=ed; j+=p) 97 { 98 if(a[j]!=b[zha++]) 99 {100 flag=1;101 break;102 }103 }104 }105 if(flag==0)106 sum++;107 }108 printf("Case #%d: %d\n",l,sum);109 }110 }111 return 0;112 }
HDU 5918 KMP/模拟
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。