title: Viterbi algorithm in linear time
body: <p>I have a problem where given a Hidden Markov model and the states S I need to find an algorithm that returns the most probable path through the Hidden Markov model for a given sequence X in time O(|S|).</p>
  
  <p>I was thinking of developing a graph where I would have all the different states at different positions in X and run a shortest path algorithm on this graph. However I will have n|S|^2 edges (where n is the number of states in X) and n|S| vertices.</p>
  
  <p>The best algorithm I have found is the acyclic shortest path which runs in time O(|E|+|V|) which is O(|S|^2) in my case. 
  Is there an algorithm I can develop for it to run in time O(|S|)? All I need is the general idea.</p>
  
  <p>Thanks</p>