来自"NOCOW"

Solution From ACcreator:

分析： 这题可以直接强套TRIE来查找匹配字符串 DP方程很好写，不过这题可以直接在TRIE查找过程中加记忆化，更容易实现。

---

Solution From format_jam: 分析：

  不難想出用DP
  在龐大的數據量的查找要求下，用哈希表系一個過得去的解法（幷非最优）

解法：DP + HASH 時間復雜度：O（n）

---

solution from flybird1 最短路径

来看样例 7325189087 5 it 18 your 9087 reality 7325189 real 7325 our 087

电话号码的每个数字表示一个结点 our 就表示从第7个点到第10个点有一条边 (注意是第6个.... 0是第8个,但起点要往前移一个) reality 就表示从第0个点到第7个点有一条边 这样,计算以0为起点, 到最后一个点的最短路径就可以了

---

solution from 小星海

[phone.pas] AC 算法：动态规划＋字符串匹配 时间：O(n^2*w+m) w取决于 Hash 和 匹配 方程：if exist(copy(s,j,i-j)) then f[i]:=min(f[i],f[j]+1); 其他：这道题方程并不难.. 单看方程的话就是NOIP 某年的弱题嘛 不过字符串有10000个...汗 我是转换成数字，存入哈希表，这样有O(1)的查找优势

Program phone;
Const Cvt               :       array ['a'..'z'] of integer
                        =       (2,2,2,3,3,3,4,4,1,1,5,5,6,6
                                ,0,7,0,7,7,8,8,8,9,9,9,0);
      HMod              =       700003;
 
Type STR                =       string[50];
     THash              =       ^TList;
     TList              =       record
                                    data  :record s:str; d:longint end;
                                    next  :THash;
                                end;
 
Var Hash                :       array [0..HMod+1] of THash;
    F,G,H,Q             :       array [0..100] of longint;
    a,b                 :       array [0..10000] of str;
    s                   :       string;
    i,j,k,n,m,r         :       longint;
 
Function MakeHash(s:str):longint;
Var i,j:longint;
Begin
    j:=0;
    for i:= 1 to length(s) do j:=(j*10+ord(s[i])-48) mod HMod;
    exit(j);
end;
 
Function Same(a,b:str):boolean;
Begin
    if a=b then exit(true) else exit(false);
end;
 
Function Exist(a:str):boolean;
Var Index:longint; v:THash;
Begin
    Index:=MakeHash(a); v:=Hash[Index];
    while (v<>nil) and not Same(v^.data.s,a) do v:=v^.next;
    if v<>nil then begin k:=v^.data.d; exit(true) end
              else exit(false);
end;
 
Procedure Add(a:str);
Var Index:longint; v:THash;
Begin
    Index:=MakeHash(a);
    new(v);
    v^.data.s:=a;
    v^.data.d:=i;
    v^.next:=Hash[Index];
    Hash[Index]:=v;
end;
 
Begin
    assign(input,'phone.in');           reset(input);
    assign(output,'phone.out');         rewrite(output);
 
    readln(s); n:=length(s);
    readln(m);
    for i:= 1 to m do
    begin
        readln(a[i]); b[i]:=a[i];
        for j:= 1 to length(a[i]) do
            a[i][j]:=chr(cvt[a[i][j]]+48);
        Add(a[i]);
    end;
 
    fillchar(f,sizeof(f),255); f[0]:=0;
    for i:= 1 to n do
    for j:= 0 to i-1 do
    if (f[j]<>-1) and (Exist(copy(s,j+1,i-j))) then
    if f[i]=-1 then
    begin
        f[i]:=f[j]+1;
        g[i]:=j;
        h[i]:=k;
    end else if f[j]+1<f[i] then
    begin
        f[i]:=f[j]+1;
        g[i]:=j;
        h[i]:=k;
    end;
 
    r:=0;
    if f[n]=-1 then writeln('No solution.') else
    begin
        j:=g[n];
        inc(r); q[r]:=h[n];
        while j<>0 do
        begin
            inc(r);
            q[r]:=h[j];
            j:=g[j];
        end;
 
        for i:= r downto 1 do
        begin
            write(b[q[i]]);
            if i<>1 then write(' ');
        end;
        writeln;
    end;
    close(input);                       close(output);
END.

再来个cpp的

#include <cstdio>
#include <cstring>
 
const int oo=50001,maxm=300;
 
int n,len[oo],L,f[maxm],pre[maxm],ans[oo],l;
char d[oo][52],phone[maxm],b[maxm];
 
inline bool check(int p,int j){
	for (int i=1;i<=len[j];i++)
	if (phone[p+i]!=b[d[j][i-1]])	return false;
	return true;
}
 
int main(){
	freopen("s.in","r",stdin);
	freopen("s.out","w",stdout);
	b['i']=b['j']='1',b['a']=b['b']=b['c']='2';b['d']=b['e']=b['f']='3';
	b['g']=b['h']='4';b['k']=b['l']='5';b['m']=b['n']='6';
	b['p']=b['r']=b['s']='7';b['t']=b['u']=b['v']='8';b['w']=b['x']=b['y']='9';b['o']=b['q']=b['z']='0';
 
	gets(phone);
	while (phone[0]!='-'){
		L=strlen(phone);
		for (int i=L;i;i--)
			phone[i]=phone[i-1];
		scanf("%d\n",&n);
		for (int i=1;i<=n;i++){
			gets(d[i]);
			len[i]=strlen(d[i]);
		}
		for (int i=1;i<=L;i++)
			f[i]=1000000000;
		memset(pre,0,sizeof(pre));
		f[0]=0;
		for (int i=0;i<L;i++)
		for (int j=1;j<=n;j++)
		if (i+len[j]<=L && f[i]+1<f[i+len[j]] && check(i,j))
			f[i+len[j]]=f[i]+1,pre[i+len[j]]=j;
		if (f[L]==1000000000)	printf("No solution.\n");
		else{
			l=0;
			for (int u=L;u;u-=len[pre[u]])
				ans[++l]=pre[u];
			for (int i=l;i;i--)
				printf("%s%c",d[ans[i]],(i!=1) ? ' ':'\n');
		}
		gets(phone);
	}
 
	return 0;
}

二分查找+dp

const c:array[1..26] of longint=(2,2,2,3,3,3,4,4,1,1,5,5,6,6,0,7,0,7,7,8,8,8,9,9,9,0);
var
f:array[-50..150] of longint;
exi:array[0..100] of boolean;
qq:array[0..100] of longint;
a,p:array[0..10,0..50000] of string;
ans:array[0..100] of string;
n:array[0..10] of longint;
len:array[0..10,0..50000] of longint;
anspre:array[0..100] of longint;
t,s,s1:string;
l,r,mid,i,j,k,m,x,max,num,qqnum:longint;
procedure qsort(l,r:longint);
var i,j:longint;s:string;
begin
i:=l;j:=r;s:=a[k,(l+r)shr 1];
repeat
	while a[k,i]<s do inc(i);
	while a[k,j]>s do dec(j);
	if i<=j then begin s1:=a[k,i];a[k,i]:=a[k,j];a[k,j]:=s1;s1:=p[k,i];p[k,i]:=p[k,j];p[k,j]:=s1;inc(i);dec(j); end;
until i>j;
if i<r then qsort(i,r); if l<j then qsort(l,j);
end;
procedure print;
var o,k:longint;
begin
s:='';k:=0;
o:=length(t);
while o>0 do
	begin
	s:=ans[o]+' '+s;
	o:=anspre[o];
	end;
writeln(s);
end;
function find(s:string; x:longint):boolean;
begin
l:=1;r:=n[x];
while l<=r do
	begin
	mid:=(L+r)shr 1;
	if a[x,mid]<s then l:=mid+1 else r:=mid-1;
	end;
if a[x,l]=s then begin num:=l; exit(true); end
	else exit(false);
end;
begin
readln(t);
for i:=-50 to 0 do f[i]:=maxint;
repeat
for i:=1 to 50 do exi[i]:=false;fillchar(qq,sizeof(qq),0);
f[0]:=0;
readln(m);
fillchar(n,sizeof(n),0); max:=0;
for i:=1 to m do
	begin
	readln(s);s1:='';
	for j:=1 to length(s) do s1:=s1+chr(c[ord(s[j])-96]+48);
	x:=ord(s1[length(s1)])-48;
	inc(n[x]);a[x,n[x]]:=s1;p[x,n[x]]:=s;
	len[x,n[x]]:=length(s);
	if max<len[x,n[x]] then max:=len[x,n[x]];
	exi[len[x,n[x]]]:=true;
	end;
for k:=0 to 9 do qsort(1,n[k]);
	qqnum:=0;
for i:=1 to 50 do if exi[i] then begin inc(qqnum);qq[qqnum]:=i; end;
for i:=1 to length(t) do
	begin
	f[i]:=maxint;
	x:=ord(t[i])-48;
	for k:=1 to qqnum do
		begin
		j:=qq[k];
		if find(copy(t,i-j+1,j),x) then
		if f[i]>f[i-j] then 
			begin
			f[i]:=f[i-j]+1;
			ans[i]:=p[x,num];
			anspre[i]:=i-j;
			end;
		end;
	end;
if f[length(t)]>=100 then writeln('No solution.') else print;
readln(t);
until t='-1';
end.