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 (835) wdqwang1 2012-04-04 21:38:12
  • Re:为何WA (973) wdqwang1 2012-04-04 21:42:12