POJ3167 Cow Patterns ——有趣的KMP算法——Pku3167

这道题还是很有意思的。题目大意如下：

给定一个模式串，如果在主串中存在这样一个子串：子串长度与模式串长度相同，且子串中各个数字的大、小、同关系和模式串中的大、小、同关系是一样的，就称该子串满足条件。

比如说模式串：1，4，4，2，3，1 而主串：5,6,2,10,10,7,3,2,9

那么主串第三位开始的2,10,10,7,3,2就是满足条件的

具体的算法很巧妙：我们对于每一个模式串中的数字要进行预处理，处理的方法很简单：分别找出三个数字作为它的定位数字：

1、前面离它最近的比它小的最大的数字的编号

2、前面离它最近但不是它本身的和它相同的数字的编号

3、前面离它最近的比它大的最小的数字的编号

 

有了这三个定位数字，就可以求出串中每个数字与它定位数字间的距离，如果距离相同，则匹配成功，否则跳到它的pre函数值上。

 

CODE

Program Cpattern;//By_thispoet
Const
	maxn=100001;
Var
	i,j,k,m,n,p,q,s						:Longint;
	st,a,rank,mins,mina,pre				:Array[0..maxn]of Longint;
	ja,js								:Array[0..maxn,0..2]of Longint;
	ans									:Array[0..maxn]of Longint;

Function Funa(i,j:Longint):Boolean;
begin
	Funa:=true;

	Funa:=Funa and ((i-ja[i,0]=j-ja[j,0])or((ja[i,0]=ja[j,0])and(ja[i,0]=-1)));
	Funa:=Funa and ((i-ja[i,1]=j-ja[j,1])or((ja[i,1]=ja[j,1])and(ja[i,1]=-1)));
	Funa:=Funa and ((i-ja[i,2]=j-ja[j,2])or((ja[i,2]=ja[j,2])and(ja[j,2]=-1)));

end;


Function Funs(i,j:Longint):Boolean;
begin
	Funs:=true;

	Funs:=Funs and ((i-js[i,0]=j-ja[j,0])or((js[i,0]=ja[j,0])and(js[i,0]=-1)));
	Funs:=Funs and ((i-js[i,1]=j-ja[j,1])or((js[i,1]=ja[j,1])and(js[i,1]=-1)));
	Funs:=Funs and ((i-js[i,2]=j-ja[j,2])or((js[i,2]=ja[j,2])and(js[i,2]=-1)));

end;


Procedure Get_ja(p,q:Longint);
var k:Longint;
begin

	fillchar(ja[p],sizeof(ja[p]),255);
	k:=a[p];

	for j:=k-1 downto 1 do
		if mina[j]>=q then
			begin
				ja[p,0]:=mina[j];
				break;
			end;

	for j:=k+1 to s do
		if mina[j]>=q then
			begin
				ja[p,2]:=mina[j];
				break;
			end;

	if (mina[k]>=q)and(mina[k]<p)then ja[p,1]:=mina[k];

end;


Procedure Kmp_Prepare;
begin

	mina[a[1]]:=1;
	pre[1]:=0;
	Get_ja(1,0);

	for i:=2 to m do
		begin

			k:=pre[i-1];

			while (k<>0) do
				begin
					Get_ja(i,i-k);

					if Funa(k+1,i) then
						begin
							pre[i]:=k+1;
							break;
						end;

					k:=pre[k];
				end;

			if k=0 then pre[i]:=1;

			Get_ja(i,0);
			mina[a[i]]:=i;

		end;

	fillchar(mina,sizeof(mina),255);

end;


Procedure Get_js(p,q:Longint);
var j,k:Longint;
begin

	fillchar(js[p],sizeof(js[p]),255);
	k:=st[p];

	for j:=k-1 downto 1 do
		if mins[j]>=q then
			begin
				js[p,0]:=mins[j];
				break;
			end;

	for j:=k+1 to s do
		if mins[j]>=q then
			begin
				js[p,2]:=mins[j];
				break;
			end;

	if (mins[k]>=q)and(mins[k]<p) then js[p,1]:=mins[k];

end;


Procedure Kmp;
var k:Longint;
begin

	p:=1;q:=1;mins[st[1]]:=1;

	while (p<n) do
		begin

			Get_js(p+1,p-q+1);

			if Funs(p+1,q+1)then
				begin
					inc(p);inc(q);
				end else
					begin
						q:=pre[q];
						while q<>0 do
							begin
								Get_js(p+1,p-q+1);
								if Funs(p+1,q+1) then
									begin
										inc(p);inc(q);
										break;
									end;
								q:=pre[q];
							end;
						if q=0 then
							begin
								inc(p);inc(q);
							end;
					end;

			mins[st[p]]:=p;

			if q=m then
				begin

					inc(ans[0]);
					ans[ans[0]]:=p-q+1;
					q:=pre[q];

				end;

		end;

end;


BEGIN

	readln(n,m,s);
	for i:=1 to n do readln(st[i]);
	for i:=1 to m do readln(a[i]);

	fillchar(mina,sizeof(mina),255);

	Kmp_Prepare;

	fillchar(mins,sizeof(mins),255);
	fillchar(js,sizeof(js),255);

	ans[0]:=0;
	Kmp;

	writeln(ans[0]);
	for i:=1 to ans[0] do writeln(ans[i]);

END.