平平带着韵韵来到了游乐园，看到了n辆漂亮的遥控车，每辆车上都有一个唯一的名字name[i]。韵韵早就迫不及待地想玩名字是s的遥控车。可是韵韵毕竟还小，她想象的名字可能是一辆车名字的前缀（也就是说能确定一个i，使s是name[i]的前缀），这时她就能玩第i辆车；或者是一个无中生有的名字，即s不是任何一辆车名字的前缀，这时候她什么也不能玩。
你需要完成下面的任务：
1.韵韵想了m个她想要的名字，请告诉她能玩多少次。
2.由于管理员粗心的操作，导致每辆车的摆放位置都可能出现微小的差错，原来第i辆车现在的位置可能是i-1、i、i+1中的任意一个（第1辆车的位置不可能是0，第n辆车的位置不可能是n+1）。请你计算出共有多少种可能的排列。
注：数据保证当s是name[i]的前缀时，i是唯一确定的。一辆车可以玩多次。
你需要完成下面的任务：
1.韵韵想了m个她想要的名字，请告诉她能玩多少次。
2.由于管理员粗心的操作，导致每辆车的摆放位置都可能出现微小的差错，原来第i辆车现在的位置可能是i-1、i、i+1中的任意一个（第1辆车的位置不可能是0，第n辆车的位置不可能是n+1）。请你计算出共有多少种可能的排列。
注：数据保证当s是name[i]的前缀时，i是唯一确定的。一辆车可以玩多次。
题解：
第一问：二分匹配
第二问：斐波那契数列f(n)位
代码：
var
i,n,m,ans,k:longint;
s:string;
a:array[0..20001] of string;
x,y,z:array[1..20000] of longint;
procedure sort(i,j:longint);
var
l,r:longint;
m:string;
begin
l:=i;
r:=j;
m:=a[(i+j) shr 1];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then
begin
a[0]:=a[i];
a[i]:=a[j];
a[j]:=a[0];
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
function search(l,r:longint):boolean;
var
temp:boolean;
mid,t:longint;
begin
search:=false;
repeat
mid:=(l+r)div 2;
if copy(a[mid],1,length(s))=s then
begin
search:=true;
t:=1;
while copy(a[mid+t],1,length(s))=s do
begin inc(ans);inc(t);end;
t:=1;
while copy(a[mid-t],1,length(s))=s do begin inc(ans);inc(t);end;
break;
end
else
begin
if l+1=r then
if copy(a[mid+1],1,length(s))=s then
inc(r)
else break;
if a[mid]>s then r:=mid
else l:=mid
end;
until l=r;
end;
procedure main;
var
i:longint;
begin
for i:=1 to k do
begin
x[i]:=x[i]+y[i];
x[i+1]:=x[i+1]+x[i] div 10;
x[i]:=x[i] mod 10;
end;
if x[k+1]<>0 then inc(k);
end;
begin
readln(n,m);
for i:=1 to n do
readln(a[i]);
sort(1,n);a[0]:='';
for i:=1 to m do
begin
readln(s);
if search(1,n) then inc(ans);
end;
writeln(ans);
k:=1;
x[1]:=1;z[1]:=1;
for i:=1 to n-1 do
begin
y:=z;z:=x;
main;
end;
for i:=k downto 1 do
write(x[i]);
end.
i,n,m,ans,k:longint;
s:string;
a:array[0..20001] of string;
x,y,z:array[1..20000] of longint;
procedure sort(i,j:longint);
var
l,r:longint;
m:string;
begin
l:=i;
r:=j;
m:=a[(i+j) shr 1];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then
begin
a[0]:=a[i];
a[i]:=a[j];
a[j]:=a[0];
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
function search(l,r:longint):boolean;
var
temp:boolean;
mid,t:longint;
begin
search:=false;
repeat
mid:=(l+r)div 2;
if copy(a[mid],1,length(s))=s then
begin
search:=true;
t:=1;
while copy(a[mid+t],1,length(s))=s do
begin inc(ans);inc(t);end;
t:=1;
while copy(a[mid-t],1,length(s))=s do begin inc(ans);inc(t);end;
break;
end
else
begin
if l+1=r then
if copy(a[mid+1],1,length(s))=s then
inc(r)
else break;
if a[mid]>s then r:=mid
else l:=mid
end;
until l=r;
end;
procedure main;
var
i:longint;
begin
for i:=1 to k do
begin
x[i]:=x[i]+y[i];
x[i+1]:=x[i+1]+x[i] div 10;
x[i]:=x[i] mod 10;
end;
if x[k+1]<>0 then inc(k);
end;
begin
readln(n,m);
for i:=1 to n do
readln(a[i]);
sort(1,n);a[0]:='';
for i:=1 to m do
begin
readln(s);
if search(1,n) then inc(ans);
end;
writeln(ans);
k:=1;
x[1]:=1;z[1]:=1;
for i:=1 to n-1 do
begin
y:=z;z:=x;
main;
end;
for i:=k downto 1 do
write(x[i]);
end.