【Poj3461】Oulipo

Source and Judge

BAPC 2006 Qualification
Poj3461
Caioj1460

Problem

【Description】
给出串A、B,判断A在B中出现次数,可重叠。
【Input】
第一行的正整数表示数据组数。
每组数据两个不包含空格的字符串表示串A、B。
【Output】
每组数据输出一个数,表示匹配个数。
【Limited conditions】
字符串仅由大写字母组成。
1 ≤ |A| ≤ 10,000
|A| ≤ |B| ≤ 1,000,000.
【Sample input】
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
【Sample output】
1
3
0
【Sample explanation】

Record

30min

Analysis1

请先思考

这道题是kmp的经典入门问题

Code1

请先思考
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
51
52
53
54
55
56
57
58
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
const int MAXN=1100000;
//*******************全局定义*******************
char a[MAXN],b[MAXN];
int la,lb;
//*******************实现*******************
int nxt[MAXN];
void prekmp()
{
lb=strlen(b+1);
for(int i=2;i<=lb;i++)
{
int j=nxt[i-1];
while(j>0 and b[j+1]!=b[i]) j=nxt[j];
if(b[j+1]==b[i]) nxt[i]=j+1;
else nxt[i]=0;
}
}
int kmp()
{
la=strlen(a+1);
int ans=0;
int j=0;
for(int i=1;i<=la;i++)
{
while(j>0 and b[j+1]!=a[i]) j=nxt[j];
if(b[j+1]==a[i]) j++;
if(j==lb) ans++;
}
return ans;
}
//*******************主函数*******************
int main()
{
//freopen("tmp.in","r",stdin);
int T;scanf("%d",&T);
while(T--)
{
scanf("%s%s",b+1,a+1);
prekmp();
printf("%d\n",kmp());
}
}

Analysis2

请先思考

然后这道题练习hash也是极好的
$S(l,r)=f[r]-b^{r-l+1}\times f[l-1]$

Code2

请先思考
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
51
52
53
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
const int MAXN=1100000;
const ull base=13331;
//*******************全局定义*******************
char a[MAXN],b[MAXN];
ull f[MAXN];
//*******************实现*******************
ull bs[MAXN];
ull getf(int l,int r)
{
return f[r]-f[l-1]*bs[r-l+1];
}
int solve()
{
int la=strlen(a+1),lb=strlen(b+1);
ull hb=0;for(int i=1;i<=lb;i++) hb=hb*base+b[i];
int ans=0;
for(int r=1;r<=la;r++)
{
f[r]=f[r-1]*base+a[r];
if(r>=lb and getf(r-lb+1,r)==hb) ans++;
}
return ans;
}
//*******************主函数*******************
int main()
{
//freopen("tmp.in","r",stdin);
bs[0]=1;for(int i=1;i<MAXN;i++) bs[i]=bs[i-1]*base;//base^i
int T;scanf("%d",&T);
while(T--)
{
scanf("%s%s",b+1,a+1);
printf("%d\n",solve());
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/Oulipo.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%