【题意】
给定n对字符串,求每组的前一个字符串在后一个字符串之中出现了几次
【输入】
第一行一个n
接下来n组数据
一组数据两行,分别是一个字符串
【输出】
对于每组数据,输出前一个字符串在后一个字符串之中出现了几次
kmp模板题,最近kmp老是编错,需要注意失效函数和next函数的意义,我写的是失效函数,就是这一位,跳到前一位的失效函数的后一个继续比较
program poj3461; var ans,l,n,i,j,k:longint; w,t:ansistring; next:array [0..10001] of longint; begin readln(n); while n>0 do begin readln(w); readln(t); l:=length(w); next[1]:=0; i:=1; j:=0; while i<l do if (j=0)or(w[i+1]=w[j+1]) then begin inc(i); if w[i]=w[j+1] then inc(j); next[i]:=j; end else j:=next[j]; w:=w+'#'; ans:=0; j:=0; for i:=1 to length(t) do begin while (j<>0)and(w[j+1]<>t[i]) do j:=next[j]; if w[j+1]=t[i] then begin inc(j); if j=l then inc(ans); end; end; writeln(ans); dec(n); end; end.