1432.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"memory.h"
#include"string.h"
char ma[][5]={".-","-...","-.-.","-..",".","..-.","--.","....",
				"..",".---","-.-",".-..","--","-.","---",".--.",
				"--.-",".-.","...","-","..-","...-",".--","-..-",
				"-.--","--.."};

char word[10000][85];
int n,m;
_int64 num[10001];
char morse[10010];
int len[10010];

void init()
{cin>>morse;
m=strlen(morse);
cin>>n;
for(int i=0;i<n;i++)cin>>word[i];

memset(num,0,(m+1)*sizeof(_int64));
}

void doword()
{int i,j;char temp[100];
for(i=0;i<n;i++)
{temp[0]=0;
 for(j=0;word[i][j]!=0;j++)strcat(temp,ma[word[i][j]-'A']);

 strcpy(word[i],temp);
len[i]=strlen(word[i]);
}
}
long answer;

void doit()
{int i=0,j,k;
num[0]=1;
for(i=0;i<m;i++)
{if(i&&num[i]==0)continue;
 for(j=0;j<n;j++)
 {for(k=0;k<len[j]&&i+k<m;k++)if(morse[i+k]!=word[j][k])break;
  if(k==len[j])num[i+len[j]]+=num[i];}
}
answer=(long)num[m];
}

int main()
{int t;
cin>>t;
while(t--)
{init();
 doword();
 doit();
 cout<<answer<<endl;
}
return 0;
}