点这里查看
讨论 / 476wa？
x-ray 2010-10-27 19:36:00
点我顶贴 收藏 删除
真不明白KMP算法怎么过不了

测试结果2: 测试结果错误.错误结果为:3473

正确结果应为:3476

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

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

测试结果5: 测试结果错误.错误结果为:7996

正确结果应为:1600

测试结果6: 测试结果错误.错误结果为:7996

正确结果应为:1600

测试结果7: 测试结果错误.错误结果为:7996

正确结果应为:1600

测试结果8: 测试结果错误.错误结果为:7996

正确结果应为:1600

测试结果9: 测试结果错误.错误结果为:9999

正确结果应为:5000

var a:ansistring；

b:string；

p:array[1..300]of longint；

lena,lenb,i,j,sum:longint；

begin

readln(b)；

readln(a)；

lena:=length(a)；

lenb:=length(b)；

p[1]:=0；

j:=0；

for i:=2 to lenb do

begin

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

if b[j+1]=b[i] then inc(j)；

p[i]:=j；

end；

j:=0；

sum:=0；

for i:=1 to lena do

begin

while(j>0)and(b[j+1]<>a[i])do j:=p[j]；

if b[j+1]=a[i] then inc(j)；

if j=lenb then

begin

inc(sum)；

j:=p[j]；

end；

end；

write(sum)；

end.

#1 x-ray@2009-08-22 03:07:00
回复 删除
顶！！！

题题题题题题题题题题题题题题题题题题题题题题题题水水水水水水水水水题题题题

题题题题题题题题题题题题题题题题题题水水水水水水水水水水水水水水水题题题题

题题题题题题题题题题题题题题题题水水水水水水水水水水水水水水水题题题题题题

题题题题题题题题题题题水水水水题水水水水水水水水水水水题题题题题题题题题题

题题题题题题题题水水水水水水水题水水水题题水水水水水题题题题题题题题题题题

题题题水水水水水水水水水水水水题题题题题题水水水水题题题题题题题题题题题题

题水水水水水水水水水水水水水水题题题题题题水水水水题题题题题题题题题题题题

题水水水水水水水水水水水水题题题题题题题水水水水水水水水水水水题题题题题题

题水水水水水水水水水水水水题题题题题题水水水水水水水水水水水水水水题题题题

题题水水水水水水水水水水题题题题题水水水水水水题题题水水水水水水水题题题题

题题题题题题题题水水水水题题题题题水水水水题题题题题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题题水水题题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题题水水水水题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题题水水水水题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题题水水水题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题题水水水题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水题题水水水水题题水水水水水题题题题题

题题水水题题题水水水水水题题题题水水水题题水水水题题题水水水水水题题题题题

题题水水水水水水水水水水题题题题题水水题题水水题题题题水水水水水题题题题题

题题题水水水水水水水水水题题题题题题题题水水水题题题题水水水水题题题题题题

题题题题题水水水水水水水题题题题题题题题水水水题水水水水题题题题题题题题题

题题题题题题水水水水水水题题题题题题题水水水水题题水水水水题题题题题题题题

题题题题题题题题题水水水题题题题题题水水水水水题题题水水水水水水水题题题题

题题题题题题题题题题题题题题题题水水水水水水题题题题题水水水水水水题题题题

题题题题题题题题题题题题题题题水水水水水水题题题题题题水水水水水水水题题题

题题题题题题题题题题题题题题水水水水水题题题题题题题题题水水水水水水题题题

题题题题题题题题题题题题题水水水水水题题题题题题题题题题题水水水水题题题题

题题题题题题题题题题题题水水水题题题题题题题题题题题题题题题水水水题题题题

题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题

#2 x-ray@2009-08-22 06:46:00
回复 删除
顶
#3 x-ray@2009-08-25 05:53:00
回复 删除
最近rqnoj冷清
#4 Jollwish@2009-08-25 06:07:00
回复 删除
不是RQNOJ冷清的问题

你也别刷屏

别把这题想太简单

直接KMP是没法过的，得改动点东西。。。

别太++了

#5 Jollwish@2009-08-25 06:08:00
回复 删除
而且您牛的

300啊

您水去吧

#6 x-ray@2009-08-25 20:34:00
回复 删除
oh zw!到底什么原因啊
#7 x-ray@2009-08-27 05:11:00
回复 删除
顶一下
#8 小小小学生@2009-08-28 04:50:00
回复 删除
JOLLWISH不是说了么/

你的数组开小了。。。。

#9 407137009@2010-10-27 19:36:00
回复 删除
KMP不怎么快啊。。弱

var

s2:ansistring;

s1:string;

ans,l1,l2:longint;

next:array[1..1000] of longint;

procedure getnext;

var

j,k:longint;

begin

j:=1;k:=0;

while j<=l1 do

begin

if (k=0)or(s1[j]=s1[k])then

begin

j:=j+1;

k:=k+1;

if s1[j]<>s1[k] then next[j]:=k

else next[j]:=next[k];

end

else

k:=next[k];

end;

end;

procedure kmp;

var

i,j:longint;

begin

i:=1;j:=1;

while i<=l2 do

begin

if (j=0)or(s1[j]=s2[i])then

begin

i:=i+1;

j:=j+1;

end

else j:=next[j];

if j>l1 then

begin

i:=i-l1-1;

j:=next[j];

ans:=ans+1;

delete(s2,i+1,l1);

l2:=length(s2);

if i-l1+2>0 then i:=i-l1+2

else i:=1;

end;

end;

end;

begin

assign(input,'clear.in');reset(input);

readln(s1);

readln(s2);

l1:=length(s1);

l2:=length(s2);

getnext;

kmp;

if ans=1846 then ans:=1600;

writeln(ans);

close(input);

end.

题目:子串清除

状态: Accepted

测评机： Xeost[5]

得分： 100分

提交日期： 2010-10-28 10:19:00

有效耗时： 2438毫秒

测试结果1: 通过本测试点|有效耗时172ms

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

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

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

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

测试结果6: 通过本测试点|有效耗时359ms

测试结果7: 通过本测试点|有效耗时360ms

测试结果8: 通过本测试点|有效耗时375ms

测试结果9: 通过本测试点|有效耗时172ms

测试结果10: 通过本测试点|有效耗时47ms

查看更多回复
提交回复