[HDU5918]Sequence I

112 阅读 0 评论 74 点赞

我是靠谱客的博主懵懂果汁，这篇文章主要介绍[HDU5918]Sequence I，现在分享给大家，希望可以做个参考。

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

Problem Description
Mr. Frog has two sequences $a_1,a_2,⋯,a_n$ and $b_1,b_2,⋯,b_m$ and a number $p$ . He wants to know the number of positions q such that sequence $b_1,b_2,⋯,b_m$ is exactly the sequence $a_q,a_{q+p},a_{q+2p},⋯,a_{q+(m−1)p}$ where $q + (m - 1) p \leq n$ and $q \geq 1$ .

Input
The first line contains only one integer $T \leq 100$ , which indicates the number of test cases.

Each test case contains three lines.

The first line contains three space-separated integers $1≤n≤10^6,1≤m≤10^6$ and $1≤p≤10^6$ .

The second line contains n integers $a_1,a_2,⋯,a_n(1≤a_i≤10^9)$ .

the third line contains m integers $b_1,b_2,⋯,b_m(1≤b_i≤10^9)$ .

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

复制代码

1
2
3
4
5
6
7
8
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

复制代码

1
2
3
Case #1: 2
Case #2: 1

题意：
给 $n, m, p$ ，再给两个数字串 $a, b$ ， $a$ 的长度为 $n$ ， $b$ 的长度为 $m$ 。问有多少个 $q > = 1$ 满足 $b_1,b_2,⋯,b_m$ 与 $a_q,a_{q+p},a_{q+2p},⋯,a_{q+(m−1)p}$ 完全一致
题解：
kmp，把 $a$ 中的元素按照 $i$ 归类，然后对于每个类当成一个串来用kmp统计这个串中有多少个与 $b$ 完全一致的子串。
注意：用kmp统计符合条件的子串个数的时候，每匹配到一个子串就要将指针向下移动一格。不然会重复计算。

复制代码

#include<bits/stdc++.h>
#define LiangJiaJun main
#define MOD 19991227
using namespace std;
int n,m,p;
int a[1000004],b[1000004],nt[1000004];
vector<int>ov[1000004];
int getnext(){
    memset(nt,0,sizeof(nt));
    int j=0;
    for(int i=2;i<=m;i++){
        while(j>0&&b[j+1]!=b[i])j=nt[j];
        if(b[j+1]==b[i])j++;
        nt[i]=j;
    }
    return 0;
}
int calc(int st){
    int j=0,res=0;
    for(int i=0;i<ov[st].size();i++){
        while(j>0&&b[j+1]!=ov[st][i])j=nt[j];
        if(b[j+1]==ov[st][i])j++;
        if(j==m){
            res++;
            j=nt[j];///记住要后移
        }
    }
    return res;
}
int w33ha(int CASE){
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)scanf("%d",&b[i]);
    getnext();
    for(int i=0;i<p;i++)if(ov[i].size()>0)ov[i].clear();
    for(int i=1;i<=n;i++)ov[i%p].push_back(a[i]);
    int ans=0;
    for(int i=0;i<p;i++){
        if(ov[i].size()>=m)ans+=calc(i);
    }
    printf("Case #%d: %dn",CASE,ans);
    return 0;
}
int LiangJiaJun(){
    int T;scanf("%d",&T);
    for(int i=1;i<=T;i++)w33ha(i);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
#define LiangJiaJun main
#define MOD 19991227
using namespace std;
int n,m,p;
int a[1000004],b[1000004],nt[1000004];
vector<int>ov[1000004];
int getnext(){
    memset(nt,0,sizeof(nt));
    int j=0;
    for(int i=2;i<=m;i++){
        while(j>0&&b[j+1]!=b[i])j=nt[j];
        if(b[j+1]==b[i])j++;
        nt[i]=j;
    }
    return 0;
}
int calc(int st){
    int j=0,res=0;
    for(int i=0;i<ov[st].size();i++){
        while(j>0&&b[j+1]!=ov[st][i])j=nt[j];
        if(b[j+1]==ov[st][i])j++;
        if(j==m){
            res++;
            j=nt[j];///记住要后移
        }
    }
    return res;
}
int w33ha(int CASE){
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)scanf("%d",&b[i]);
    getnext();
    for(int i=0;i<p;i++)if(ov[i].size()>0)ov[i].clear();
    for(int i=1;i<=n;i++)ov[i%p].push_back(a[i]);
    int ans=0;
    for(int i=0;i<p;i++){
        if(ov[i].size()>=m)ans+=calc(i);
    }
    printf("Case #%d: %dn",CASE,ans);
    return 0;
}
int LiangJiaJun(){
    int T;scanf("%d",&T);
    for(int i=1;i<=T;i++)w33ha(i);
    return 0;
}