Tang-Dreamoon's Blog

poj 3167

发表于 | 分类于 ， ，

另类KMP

　　题目链接：poj 3167

　　题意：给定主串 S 和模式串 P ，均由数字 1~25 组成。定义串 A 与串 B 相等，当且仅当两个串长度相等，且对于任意 i，第 i 个数在各自串的前 i 个数中排名相等；按照上述要求进行匹配，输出在哪几个位置可以匹配成功。

　　题解：首先思考如何算排名相等。我们可以发现如果排名相等那么两个串中比 i 小的数的个数一定相等而且和 i 一样的数的个数一定也相等。因为数的种类很少，所以我们就可以用前缀和来快速的求出“i 的排名”，并以此为新的等于条件然后进行 KMP 就好了。

　　我思故我在：膜拜大佬 SXY 。

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,k;
int a[100100],b[25500];
int aa[100100][30],bb[25500][30];
int aaa[100100][30],bbb[25500][30];
int next[25500];
int stack[100100];
int tot=0;
void make()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			if(a[i]==j) aa[i][j]=aa[i-1][j]+1;
			else aa[i][j]=aa[i-1][j];
			if(a[i]<j) aaa[i][j]=aaa[i-1][j]+1;
			else aaa[i][j]=aaa[i-1][j];
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=k;j++)
		{
			if(b[i]==j) bb[i][j]=bb[i-1][j]+1;
			else bb[i][j]=bb[i-1][j];
			if(b[i]<j) bbb[i][j]=bbb[i-1][j]+1;
			else bbb[i][j]=bbb[i-1][j];
		}
	}
}
void work()
{
	next[1]=0;
	int j=0;
	for(int i=2;i<=m;i++)
	{
		while(j&&(bb[j+1][b[j+1]]!=(bb[i][b[i]]-bb[i-j-1][b[i]])||bbb[j+1][b[j+1]]!=(bbb[i][b[i]]-bbb[i-j-1][b[i]])))	j=next[j];
		if((bb[j+1][b[j+1]]==(bb[i][b[i]]-bb[i-j-1][b[i]]))&&(bbb[j+1][b[j+1]]==(bbb[i][b[i]]-bbb[i-j-1][b[i]]))) j++;
		next[i]=j;
	}
}
void anss()
{
	int i=1,j=1;
	while(i<=n)
	{
//		cout<<j<<endl;
//		cout<<(aa[i][a[i]]-aa[i-j][a[i]])<<" "<<bb[j][b[j]]<<endl;
		if((aa[i][a[i]]-aa[i-j][a[i]]==bb[j][b[j]])&&(aaa[i][a[i]]-aaa[i-j][a[i]]==bbb[j][b[j]])) i++,j++;
		else
		{
			j--;
			while(j&&((aa[i][a[i]]-aa[i-j-1][a[i]]!=bb[j+1][b[j+1]])||(aaa[i][a[i]]-aaa[i-j-1][a[i]]!=bbb[j+1][b[j+1]])))	j=next[j];
			if((aa[i][a[i]]-aa[i-j-1][a[i]]==bb[j+1][b[j+1]])&&(aaa[i][a[i]]-aaa[i-j-1][a[i]]==bbb[j+1][b[j+1]])) j++;
			i++,j++;
		}
		if(j==m+1)
		{
			stack[++tot]=i-j+1;
			j=next[j-1]+1;
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
		scanf("%d",&b[i]);
	make();
	work();
	anss();
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++)
		printf("%d\n",stack[i]);
	return 0;
}