讨论 / KMP 为什么只过5个点???
火舞逆天 2011-10-26 22:17:00
点我顶贴 收藏 删除
测试结果1: 通过本测试点|有效耗时78ms

测试结果2: 通过本测试点|有效耗时62ms

测试结果3: 通过本测试点|有效耗时63ms

测试结果4: 通过本测试点|有效耗时218ms

测试结果5: 通过本测试点|有效耗时234ms

测试结果6: 选手程序运行超过时限

测试结果7: 输出过长|用户输出数据超过标准输出两倍[标准输出4位|选手输出18位]

测试结果8: 输出过少|用户输出数据少于标准输出的50%[标准输出206303位|选手输出18位]

测试结果9: 选手程序运行超过时限

测试结果10: 输出过长|用户输出数据超过标准输出两倍[标准输出18位|选手输出297780位]

program t397;

var st,st1,stt:ansistring;

n,m,i,j,k,tol:longint;

min,max:char;

ans,p:array[0..200000] of longint;

procedure qsort(s,t:longint);

var i,j,x:longint;

begin

i:=s; j:=t; x:=ans[i];

while i<j do

begin

while (i<j)and(x<ans[j]) do dec(j);

if i<j then

begin

ans[i]:=ans[j];

inc(i);

end;

while (i<j)and(x>ans[i]) do inc(i);

if i<j then

begin

ans[j]:=ans[i];

dec(j);

end;

ans[i]:=x;

end;

if s<i-1 then qsort(s,i-1);

if i+1<t then qsort(i+1,t);

end;

begin

readln(st);

readln(st1);

m:=length(st);

n:=length(st1);

j:=0; p[1]:=0;{预处理}

for i:=2 to m do

begin

while (j>0)and(st[i]<>st[j+1]) do j:=p[j];

if st[i]=st[j+1] then inc(j);

p[i]:=j;

end;

max:='a'; min:='z';

for i:=1 to m do

begin

if st[i]>max then max:=st[i];

if st[i]<min then min:=st[i];

end;

for i:=(ord('a')-ord(min)) to (ord('z')-ord(max)) do

begin

stt:=st;

for j:=1 to m do

stt[j]:=chr(ord(st[j])+i);

j:=0;

for k:=1 to n do{KMP}

begin

while (j>0)and(st1[k]<>stt[j+1]) do j:=p[j];

if st1[k]=stt[j+1] then inc(j);

if j=m then

begin

inc(tol);

ans[tol]:=k+1-m;

j:=p[j];

end;

end;

end;

qsort(1,tol);

if tol=0 then writeln('WZY died of twins!') else

begin

writeln(tol);

for i:=1 to tol do

writeln(ans[i]);

end;

end.

查看更多回复
提交回复