Bzoj|Bzoj 1729 [Usaco2005 dec] Cow Patterns 牛的模式匹配
【Bzoj|Bzoj 1729 [Usaco2005 dec] Cow Patterns 牛的模式匹配】原题网址：http://www.lydsy.com/JudgeOnline/problem.php?id=1729
http://poj.org/problem?id=3167
这题类似kmp，但匹配的时候不是直接的关键字匹配，而是排名的匹配，在kmp的基础上，每次比较相同或不同不是直接的关键字比较，而是用树状数组统计小于当前数和等于当前数的数量，如果对应相同，即排名相同。
const
MX=25;
MXN=100050;
var
tr1,tr2:array[0..MX] of longint;
a,b,p,match,rec:array[0..MXN] of longint;
n,m,i,j,k,cnt,s:longint;
procedure change1(x,k:longint);
begin
while (x<=MX) do
begin
inc(tr1[x],k);
x:=x + x and (-x);
end;
end;
procedure change2(x,k:longint);
begin
while (x<=MX) do
begin
inc(tr2[x],k);
x:=x + x and (-x);
end;
end;
function query1(x:longint):longint;
begin
query1:=0;
while (x>0) do
begin
inc(query1,tr1[x]);
x:=x - x and (-x);
end;
end;
function query2(x:longint):longint;
begin
query2:=0;
while (x>0) do
begin
inc(query2,tr2[x]);
x:=x - x and (-x);
end;
end;
begin
read(n,m,s);
for i:=1 to n do read(a[i]);
for i:=1 to m do read(b[i]);
fillchar(tr1,sizeof(tr1),0);
fillchar(tr2,sizeof(tr2),0);
p[1]:=0;
j:=0;
for i:=2 to m do
begin
while (j>0)and((query1(b[j+1]-1)<>query2(b[i]-1))or(query1(b[j+1])<>query2(b[i]))) do
begin
for k:=p[j]+1 to j do change1(b[k],-1);
for k:=i-j to i-p[j]-1 do change2(b[k],-1);
j:=p[j];
end;
if (query1(b[j+1]-1)=query2(b[i]-1))and(query1(b[j+1])=query2(b[i])) then
begin
change1(b[j+1],1);
change2(b[i],1);
inc(j);
end;
p[i]:=j;
end;
fillchar(tr1,sizeof(tr1),0);
fillchar(tr2,sizeof(tr2),0);
match[1]:=0;
j:=0;
for i:=1 to n do
begin
while (j>0)and((query1(b[j+1]-1)<>query2(a[i]-1))or(query1(b[j+1])<>query2(a[i]))) do
begin
for k:=p[j]+1 to j do change1(b[k],-1);
for k:=i-j to i-p[j]-1 do change2(a[k],-1);
j:=p[j];
end;
if (query1(b[j+1]-1)=query2(a[i]-1))and(query1(b[j+1])=query2(a[i])) then
begin
change1(b[j+1],1);
change2(a[i],1);
inc(j);
end;
match[i]:=j;
if (j=m) then
begin
inc(cnt);
rec[cnt]:=i-m+1;
for k:=p[j]+1 to j do change1(b[k],-1);
for k:=i-j+1 to i-p[j] do change2(a[k],-1);
j:=p[j];
end;
end;
writeln(cnt);
for i:=1 to cnt do
writeln(rec[i]);
end.
推荐阅读
- 【BZOJ】4316:|【BZOJ】4316: 小C的独立集 静态仙人掌
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN
- bzoj|Bzoj3817:Sum
- BZOJ|BZOJ2763[JLOI2011]飞行路线【分层图最短路】
- BZOJ3817（Sum（类欧几里得））
- 类欧几里得|bzoj2987 Earthquake 类欧几里得
- 题解|[BZOJ3817] Sum
- bzoj2712 -- 类欧几里得算法
- Bzoj|[BZOJ2187][fraction][类欧几里得算法]