poj 2185 (KMP)

完全不会啊……

附一份题解:http://blog.sina.com.cn/s/blog_69c3f0410100tyjl.html

 var i,j,k,r,c,x:longint;
ch:array[..,..] of char;
s:string;
rr,cc:array[..] of boolean;
pre:array[..] of longint;
procedure init;
begin
readln(r,c);
for i:= to r do
begin
readln(s);
for j:= to c do ch[i,j]:=s[j];
end;
end;
procedure main;
begin
fillchar(rr,sizeof(rr),true);
fillchar(cc,sizeof(cc),true);
for x:= to r do
begin
pre[]:=;k:=;
for i:= to c do
begin
while (k<>) and (ch[x,k+]<>ch[x,i]) do k:=pre[k];
if ch[x,k+]=ch[x,i] then inc(k);
pre[i]:=k;
end;
k:=c;
for i:= to c do
if c-pre[k]<>i then cc[i]:=false else k:=pre[k];
end;
for x:= to c do
begin
pre[]:=;k:=;
for i:= to r do
begin
while (k<>) and (ch[k+,x]<>ch[i,x]) do k:=pre[k];
if ch[k+,x]=ch[i,x] then inc(k);
pre[i]:=k;
end;
k:=r;
for i:= to r do
if r-pre[k]<>i then rr[i]:=false else k:=pre[k];
end;
for i:= to r do if rr[i] then break;
for j:= to c do if cc[j] then break;
writeln(i*j);
end;
begin
init;
main;
end.

if c-pre[k]<>i then cc[i]:=false else k:=pre[k];

if r-pre[k]<>i then rr[i]:=false else k:=pre[k];

这两句话到底什么意思?

上一篇:left join测试验证之一


下一篇:[CareerCup] 6.3 Water Jug 水罐问题