> var
>   n,i : longint;
>   s,t : ansistring;
>   next : array[1..100000] of longint;
> 
> procedure compute_next;
> var
>   k,q : integer;
> begin
>   k := 0; next[1] := 0;
>   for q := 2 to length(t) do begin
>     while (k > 0) and (t[q] <> t[k+1]) do k := next[k];
>     if t[q] = t[k+1] then inc(k);
>     next[q] := k;
>   end;
> end;
> 
> function kmp : longint;
> var
>   k,q : integer;
> begin
>   compute_next;
>   k := 0; kmp := 0;
>   for q := 1 to length(s) do begin
>     while (k > 0) and (s[q] <> t[k+1]) do k := next[k];
>     if s[q] = t[k+1] then inc(k);
>     if k = length(t) then begin
>       inc(kmp);
>       k := next[k];
>     end;
>   end;
> end;
> 
> begin
>   readln(n);
>   for i := 1 to n do begin
>     readln(t); readln(s);
>     writeln(kmp);
>   end;
> end.

• Re:为何WA (973) wdqwang1 2012-04-04 21:42:12