title: Sliding window searching algorithm
body: <p>I am in need of a data storage type and algorithm for keeping track of the status of the last N items I have seen.  Each item has a status of Pass or Fail, but the system I am monitoring will deemed to have failed if M items in a row have failed.  Once the system is deemed to have failed I then need to scan back through the history of data and find the last window of width W in which all items had a "good" status.</p>
  
  <p>For example, with a M=4 and W = 3:</p>
  
  <pre>
      1 Good
      2 Good
      3 Good
      4 Good
      5 Good |
      6 Good |- Window of size 3 where all are good.
      7 Good |
      8 Bad
      9 Bad
      10 Good
      11 Good
      12 Bad
      13 Good
      14 Bad
      15 Bad
      16 Bad
      17 Bad  &lt;== System is deemed bad at this point  So scan backwards to find "Good" window.
  </pre>
  
  <p>I know that this is going to end up in something like a regular expression search and have vague recollections of Knuth floating up out the dark recesses of my memory, so could anyone point me towards a simple introduction on how to do this?   Also for what it is worth I will be implementing this in C# .Net 3.5 on a Windows XP system seeing 3GB of Ram (and an i7 processor - <em>sniff</em> the machine used to have Windows 7 and it does have 8GB of memory - but that <em>was</em> a story for TDWTF)</p>
  
  <p>Finally I will be scanning numbers of items in the 100,000's to millions in any given run of this system.  I won't need to keep track of the entire run, just the subset of all items until a system failure occurs.  When that happens I can dump all my collected data and start the process all over again.  However for each item I am tracking, I will have to keep at least the pass/fail status, and a 10 char string.  So I am looking for suggestions on how to collect and maintain this data in the system as well.  Although I am tempted to say - "meh, it will all fit in memory even if the entire run pass with 100%, so its off to an array for you!"</p>