title: Efficient way to tokenize a string - C
body: <p>I am trying to tokenize a string. I have a table of available tokens ordered in the form of a <em>trie</em>. Each token knows it has children. A simple tokens table will look like,</p>
  
  <pre><code>pattern    value         has_children
  --------   ------        --------
  s          s-val         1
  stack      stack-val     0
  over       over-val      1
  overflow   overflow-val  0
  </code></pre>
  
  <p>In this table, <code>stack</code> is a child of <code>s</code> and <code>overflow</code> is a child of <code>over</code>. In practice, this table will have 5000+ records ordered in this way. </p>
  
  <p>Now, given a string <code>stackover</code>, it should output <code>stack-valover-val</code>. Algorithm is greedy and it will try to find the longest match always. </p>
  
  <p>To do this, I will start reading each character from the input, look for match, if a match found and the token has children, look for match again by including next character. Do this until we find the longest match. If no match found, try to match by including the next character until we reach the end of string or a successful match. </p>
  
  <p>If we reached end of the string without a match, output <code>?</code> symbol and remove the first character from the input. Repeat the whole process with remaining characters.</p>
  
  <p>This algorithm works, but the backtracking and iterating on all possible combinations of the input makes it slow and complex. </p>
  
  <p>I am wondering is there a better way of solving this? Any help would be appreciated. </p>