title: Finding smallest substring not present in string
body: <p>I have a string consisting only of digits 0-9. The string can be between 1 and 1,000,000 characters in length. I need to find the smallest number that isn't present in the string, in linear time. Here are some examples: </p>
  
  <pre><code>1023456789       //Smallest number not in string is 11
  1023479          //Smallest number not in string is 5
  112131405678910  //Smallest number not in string is 15
  </code></pre>
  
  <p>With size of 1,000,000, I figured that the smallest number not present in the string has to be at most 6 digits.</p>
  
  <p>My approach was to generate all numbers 0 through 999,999 and insert them all in a vector (in order). Then make a map that marks what strings have already been seen. Then I iterate through the string, and for each position I get all substring starting from it, size 1 to 6, and I mark all those substrings as true in the map. At the end, I just check all keys one by one, and when I find the first one that has a false value in the map, I print it.</p>
  
  <p>Here are some code snippets: </p>
  
  <pre><code>string tmp="0";
  string numbers[999999];
  
  void increase(int pos)
  {
      if(pos==-1)tmp.insert(0,"1");
      else if(tmp.at(pos)!='9')tmp.at(pos)++;
      else
      {
          tmp.at(pos)='0';
          increase(pos-1);
      }
  }
  
  //And later inside main
  for(int j=0;j&lt;999999;j++)
  {
      numbers[j]=tmp;
      increase(tmp.size()-1);
  }
  </code></pre>
  
  <hr>
  
  <pre><code>for(int j=0;j&lt;input.size();j++)
      {
          for(int k=0;k&lt;6;k++)
          {
              string temp="";
              if(j+k&lt;input.size())
              {
                  temp+=input.at(j+k);
                  appeared[temp]=true;
              }
          }
      }
  </code></pre>
  
  <hr>
  
  <pre><code>int counter=0;
  while(appeared[numbers[counter]])counter++;
  cout&lt;&lt;numbers[counter]&lt;&lt;endl;
  </code></pre>
  
  <p>A note about the first part of the algorithm. I generate the vector once, then I use it for 100 strings. I need to parse all 100 strings in less than 4 seconds.</p>
  
  <p>This algorithm is too slow for me as it is currently. Could I optimize some of the code, or should I consider a different approach?</p>