## 1113 - Multiple Morse Matches

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### 1113 - Multiple Morse Matches

For the sample input, the two phrases that can be formed are:
AT TACK AT DAWN
ATTACK AT DAWN

The extra space makes them distinct.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 1113 - Multiple Morse Matches

Code: Select all

``````#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
using namespace std;

// Define Some Variables
#define eps 1e-14
#define si 10010
#define pi acos(-1.0)
#define inf (1<<30)-1
#define mod 1000000000 //10^9

//Define Some Functions
#define even(a) ((a)%2==0)
#define odd(a) ((a)%2==1)
#define max(a,b) (a>b ?a:b)
#define min(a,b) (a<b ?a:b)
#define pb push_back
#define mpair make_pair
#define sqr(a)((a)*(a))
#define area(x1,y1,x2,y2,x3,y3) (x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)) //Area of a triangle
#define dist(x1,y1,x2,y2) (sqr(x1-x2)+sqr(y1-y2)) //Distance between two points
#define mem(a,v) memset(a,v,sizeof(a))
inline bool compare( double a, double b ) { return fabs( a-b ) < eps ; }
#define fr(i,a,b) for(i=a;i<=b;i++)
#define rep(i,a,b) for(i=a;i<b;i++)
#define rev(i,a,b)  for(i=a;i>=b;i--)

typedef long long i64;

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int i,j,l,n,cs=1;
char ch[si],st[1010];
map<string,char>mp;

struct node
{
int mrk,sv;

node *nxt[26];

node()
{
int i;
rep(i,0,26)
nxt[i]=0;

mrk=0;
sv=-1;
}
}*root;

void insert()
{
node *nw=root;
int i,j;
rep(i,0,l)
{
j=ch[i]-65;
if(!(nw->nxt[j]))
nw->nxt[j]=new node();
nw=nw->nxt[j];
}
nw->mrk=1;
}

int query(node *nw,node *start,int ind)
{
if(ind==l&&start!=root)
return 1;
if(ind==l)
return 0;

if(nw->sv!=-1)
return nw->sv;

string chk;
char c;
int j,ret=0,i,p;
rep(i,ind,l)
{
chk+=st[i];
if(mp[chk])
{
c=mp[chk];
j=c-65;
if(nw->nxt[j])
{
p=query(nw->nxt[j],start,i+1);
if(p>0)
ret+=p;
}
}
}
if(nw->mrk)
ret+=query(root,nw,ind);

if(nw==start)
nw->sv=ret;
return ret;
}

int main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);

mp[".-"]='A';
mp["-..."]='B';
mp["-.-."]='C';
mp["-.."]='D';
mp["."]='E';
mp["..-."]='F';
mp["--."]='G';
mp["...."]='H';
mp[".."]='I';
mp[".---"]='J';
mp["-.-"]='K';
mp[".-.."]='L';
mp["--"]='M';
mp["-."]='N';
mp["---"]='O';
mp[".--."]='P';
mp["--.-"]='Q';
mp[".-."]='R';
mp["..."]='S';
mp["-"]='T';
mp["..-"]='U';
mp["...-"]='V';
mp[".--"]='W';
mp["-..-"]='X';
mp["-.--"]='Y';
mp["--.."]='Z';

int t;
scanf("%d",&t);
while(t--)
{
scanf("%s%d",st,&n);
root=new node();
while(n--)
{
scanf("%s",ch);
l=strlen(ch);
insert();
}
l=strlen(st);
int ans=query(root,root,0);
printf("%d\n",ans);
if(t)
puts("");
}
return 0;
}
``````