首页 > 代码库 > Sequence I

Sequence I

2024-09-21 07:15:29   218人阅读

 

Sequence I (hdu 5918)

 

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1938    Accepted Submission(s): 730


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,?,bmis 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 21
3 2 2 3 11
2 3

 

Sample Output

Case #1: 2

Case #2: 1

 

 

//题意: 字符串匹配，就是，n 长主串，m 长匹配串，k 长间隔，问有多少种匹配?

分成 k 组就好，这题可以用来测测你的 KMP 模板哦，数据还可以，就是，就算是朴素匹配也能过。。。

做完我算是真的理解KMP了，对于字符串，有个 \0 结尾的特性，所以优化的 next 是可行的，但是这种却不行，而且，优化的并不好求匹配数。

 KMP 模板 : http://www.cnblogs.com/haoabcd2010/p/6722073.html

技术分享
 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <vector> 5 using namespace std; 6 #define MX 1000005 7  8 int n,m,p; 9 int ans;10 int t[MX];11 vector<int> zu[MX];12 int net[MX];13 14 void Init()15 {16     for (int i=0;i<=n;i++)17         zu[i].clear();18 }19 20 void get_next()21 {22     int i=0,j=-1;23     net[0]=-1;24     while (i<m)25     {26         if (j==-1||t[i]==t[j]) net[++i]=++j;27         else j = net[j];28     }29 30     for (int i=0;i<=m;i++)31         printf("%d ",net[i]);32     printf("\n");33 }34 35 void KMP(int x)36 {37     int i=0,j=0;38     int len = zu[x].size();39     while(i<len&&j<m)40     {41         if (j==-1||zu[x][i]==t[j])42         {43             i++,j++;44         }45         else j=net[j];46         if (j==m)47         {48             ans++;49             j = net[j];50         }51     }52 }53 54 int main()55 {56     int T;57     scanf("%d",&T);58     for(int cas=1;cas<=T;cas++)59     {60         scanf("%d%d%d",&n,&m,&p);61         Init();62         for (int i=0;i<n;i++)63         {64             int x;65             scanf("%d",&x);66             zu[i%p].push_back(x);67         }68         for (int i=0;i<m;i++)69             scanf("%d",&t[i]);70         get_next();71 72         ans = 0;73         for (int i=0;i<p;i++) KMP(i);74         printf("Case #%d: %d\n",cas,ans);75     }76     return 0;77 }
View Code

 

 

 

 

Sequence I


联系
我们