ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1423. String Tale

Why do I have WA#8 using KMP? Help me, please... (+)
Posted by Alexey 25 Aug 2006 19:25
[deleted]

Procedure Prefix;
Var i,kk:longint;
Begin
  kk:=0;
  For i:=2 to n do
  Begin
    While (kk>0) and (a[kk+1]<>a[i]) do kk:=p[kk];
    If a[kk+1]=b[i] then inc(kk);
    p[i]:=kk;
  End;
End;

[deleted]

Thanks.

Edited by author 27.08.2006 12:38
Re: Why do I have WA#8 using KMP? Help me, please... (+)
Posted by Giorgi Saghinadze (Tbilisi SU) 26 Aug 2006 00:57
your prefix function change 'b' whith 'a' and get AC

If a[kk+1]=b[i] then inc(kk) -> If a[kk+1]=a[i] then inc(kk)
Re: Why do I have WA#8 using KMP? Help me, please... (+)
Posted by Alexey 27 Aug 2006 12:37
Oh, thanks!
What a stupid mistake!
I must be more attentive!
Re: Why do I have WA#8 using KMP? Help me, please... (+)
Posted by Vukasin 1 Jun 2008 07:43
Someone knows what is that test?
give me some tests please...
Why do I have Crash acces violation on #8?
Posted by Marija 5 Jun 2008 16:02
program stringtale;
var x,y:array[1..10000] of char;
n,i,s:integer;t:boolean;p:char;
  Begin
    readln(n);
    for i:=1 to n do read(x[i]);readln;
    for i:=1 to n do read(y[i]);s:=0;t:=false;
    while (not t) and (s<n) do
      Begin
        t:=true;
        for i:=1 to n do
          if x[i]<>y[i] then t:=false;
        s:=s+1;
        p:=x[n];
        for i:=n downto 2 do x[i]:=x[i-1];
        x[1]:=p;
      End;
    if t then write(s-1)
      else write('-1');
  End.
Re: Why do I have Crash acces violation on #8?
Posted by Max (Pskov) 18 Jun 2008 02:10
because your program not works for n>=32000(integer) but n maybe 250000. And x and y in your program very short - 10000, but maybe 250000