1113 - Multiple Morse Matches

[brianfry713]

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.

[Mukit Chowdhury]

Getting WA !!! Help please...

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;
}