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

WA#6 using KMP. Can anyone help me?
Posted by williamljb 30 Apr 2009 11:38
program p1423;
var
  p:array[0..250000]of longint;
  a,b:array[0..250000]of char;
  i,j,k,n,m:longint;
begin
  readln(n);
  for i:=1 to n do
    read(b[i]);
  readln;
  for i:=1 to n do
    read(a[i]);
  readln;
  p[1]:=0;
  j:=0;
  for i:=2 to n do
    begin
      while(j>0)and(b[j+1]<>b[i])do
        j:=p[j];
      if b[j+1]=b[i]
        then j:=j+1;
      p[i]:=j;
    end;
  j:=0;
  for i:=1 to n do
    begin
      while(j>0)and(b[j+1]<>a[i])do
        j:=p[j];
      if b[j+1]=a[i]
        then j:=j+1;
    end;
  if j=n
    then begin
      writeln(0);
      halt;
    end;
  if j<>0
    then writeln(n-j)
    else writeln(-1);
end.

Thanks for helping!
Sorry for my English...
Re: WA#6 using KMP. Can anyone help me?
Posted by [LG]_#\#@P$T[101]R 30 Apr 2009 14:42
read string S, read string T, S := S + S, prefix, kmp and AC :)
Re: WA#6 using KMP. Can anyone help me?
Posted by Proba 29 Aug 2010 16:40
s = s + s. I got AC.