记录编号	94259	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	dxc4598	是否通过	通过
代码语言	Pascal	运行时间	0.070 s
提交时间	2014-03-31 12:14:34	内存使用	0.18 MiB

var
  a,b:ansistring;
  next:array[1..10000]of integer;
  ans,len,n,i:longint;

procedure getnext;
var
  i,j:longint;
begin
  j:=0; next[1]:=0;
  for i:=2 to len do
    begin
      while (j<>0)and(a[j+1]<>a[i]) do j:=next[j];
      if a[j+1]=a[i] then inc(j);
      next[i]:=j;
    end;
end;

procedure main;
var
  i,j:longint;
begin
  j:=0;
  for i:=1 to length(b) do
    begin
      while (j<>0)and(a[j+1]<>b[i]) do j:=next[j];
      if a[j+1]=b[i] then
        begin
          inc(j);
          if j=len then inc(ans);
        end;
    end;
end;

begin
assign(input,'oulipo.in');
reset(input);
assign(output,'oulipo.out');
rewrite(output);
  readln(n);
  for i:=1 to n do
    begin
      readln(a); readln(b); ans:=0; fillchar(next,sizeof(next),0);
      len:=length(a); getnext;
      a:=a+'&';
      main;
      writeln(ans);
    end;
close(input);
close(output);
end.