|
|
back to boardWong answer#16! What's wrong? Posted by PanYe 11 Aug 2006 09:19 Program KMP; Const Maxn=250000; Var i,j,n,k,l,ans:Longint; S,T:ansistring; Next:array[0..Maxn] of Longint; Begin Readln(N); Readln(S); Readln(T); S:=S+S; Next[0]:=0;Next[1]:=0;k:=0; For i:=2 to length(T) Do Begin While (k>0) And (T[i]<>T[k+1]) Do K:=Next[k]; If (T[i]=T[k+1]) Then Inc(K); Next[i]:=k; End; I:=1;j:=1; While I<=length(S) Do Begin L:=I; While (i<=2*n) And (j<=n) And (S[I]=T[J]) Do Begin Inc(i);Inc(J); End; Ans:=i-n; If J=n+1 Then Break; If J=1 Then I:=L+1 Else I:=L+J-1-Next[j-1]; J:=Next[J-1]+1; End; l:=Ans; If n-l+1=n Then Writeln(0) Else If i>length(S) Then Writeln(-1) Else Writeln(n-l+1); End. Re: Wong answer#16! What's wrong? Posted by Lomir 21 Jan 2007 23:06 Solving this problem I was caught by all triky tests (WA6, WA8, WA16). So test 16 is something like this: 6 aabaaa aaabaa Answer is: 1 Your program, like mine at first, would output 5, i think. |
|
|