title: Parsing morse code
body: <p>I am trying to solve <a href="http://uva.onlinejudge.org/index.php?option=onlinejudge&amp;page=show_problem&amp;problem=3554" rel="nofollow">this problem</a>.
  The goal is to determine the number of ways a morse string can be interpreted, given a dictionary of word.
  What I did is that I first "translated" words from my dictionary into morse. Then, I used a naive algorithm, searching for all the ways it can be interpreted recursively.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;map&gt;
  #include &lt;string&gt;
  #include &lt;iterator&gt;
  using namespace std;
  
  string morse_string;
  int morse_string_size;
  map&lt;char, string&gt; morse_table;
  unsigned int sol;
  
  void matches(int i, int factor, vector&lt;string&gt; &amp;dictionary) {
      int suffix_length = morse_string_size-i;
      if (suffix_length &lt;= 0) {
          sol += factor;
          return;
      }
      map&lt;int, int&gt; c;
      for (vector&lt;string&gt;::iterator it = dictionary.begin() ; it != dictionary.end() ; it++) {
          if (((*it).size() &lt;= suffix_length) &amp;&amp; (morse_string.substr(i, (*it).size()) == *it)) {
              if (c.find((*it).size()) == c.end())
                  c[(*it).size()] = 0;
              else
                  c[(*it).size()]++;
          }
      }
  
      for (map&lt;int, int&gt;::iterator it = c.begin() ; it != c.end() ; it++) {
          matches(i+it-&gt;first, factor*(it-&gt;second), dictionary);
      }
  }
  
  string encode_morse(string s) {
      string ret = "";
      for (unsigned int i = 0 ; i &lt; s.length() ; ++i) {
          ret += morse_table[s[i]];
      }
      return ret;
  }
  
  int main() {
      morse_table['A'] = ".-"; morse_table['B'] = "-..."; morse_table['C'] = "-.-."; morse_table['D'] = "-.."; morse_table['E'] = "."; morse_table['F'] = "..-."; morse_table['G'] = "--."; morse_table['H'] = "...."; morse_table['I'] = ".."; morse_table['J'] = ".---"; morse_table['K'] = "-.-"; morse_table['L'] = ".-.."; morse_table['M'] = "--"; morse_table['N'] = "-."; morse_table['O'] = "---"; morse_table['P'] = ".--."; morse_table['Q'] = "--.-"; morse_table['R'] = ".-."; morse_table['S'] = "..."; morse_table['T'] = "-"; morse_table['U'] = "..-"; morse_table['V'] = "...-"; morse_table['W'] = ".--"; morse_table['X'] = "-..-"; morse_table['Y'] = "-.--"; morse_table['Z'] = "--..";
      int T, N;
      string tmp;
      vector&lt;string&gt; dictionary;
      cin &gt;&gt; T;
  
      while (T--) {
          morse_string = "";
          cin &gt;&gt; morse_string;
          morse_string_size = morse_string.size();
          cin &gt;&gt; N;
          for (int j = 0 ; j &lt; N ; j++) {
              cin &gt;&gt; tmp;
              dictionary.push_back(encode_morse(tmp));
          }
  
          sol = 0;
          matches(0, 1, dictionary);
          cout &lt;&lt; sol;
  
          if (T)
              cout &lt;&lt; endl &lt;&lt; endl;
      }
  
      return 0;
  }
  </code></pre>
  
  <p>Now the thing is that I only have 3 seconds of execution time allowed, and my algorithm won't work under this limit of time.</p>
  
  <p>Is this the good way to do this and if so, what am I missing ? Otherwise, can you give some hints about what is a good strategy ?</p>
  
  <p>EDIT :
  There can be at most 10 000 words in the dictionary and at most 1000 characters in the morse string.</p>