Most efficient way to test if a string contains a word?
Xichekolas: EDIT: Revised running time and added code (in Ruby)Build a Trie out of your dictionary. Then plug your string into and record depth/chars where it deadends. Repeat for you string with the first char removed. At the end you should have the longest substring.Minor optimization would be to stop plugging things into the Trie once the remaining characters in the string are less than the longest word you have already found.This should run in linear time (relative to your search string) because the recursion is limited by the longest word in the dictionary (depth of the trie). I have tested this out just for fun.First I grabbed the Wikipedia page for 'line of succession to the British throne' and stripped it down to text only (352,000 chars). Then I added 'monarch' to my dictionary. Then I took the first 10k chars of the text and put it into my trie, getting back monarch as my match and timing it. Then I figured the ratio of time taken to size of string (10k). I repeated this for 20k chars, 30k chars ... 350k chars, and the ratio remains constant, indicating time increases in proportion to string length... linear time.  DICTIONARY = %w(a ants apple bear bicycle)
  
  class LameTrie
    def initialize(dict)
      @trie = {}
  
      dict.each {|word| insert(word) }
      # obviously it'd be nice to only build this once
      # and then write it out to disk, since our
      # dictionary probably won't change much
    end
    
    def insert(word, level = @trie)
      c, rest = h_t(word)
      level[c] = {} unless level.has_key?(c)
      if rest.empty?
        level[c][:term] = true
      else
        insert(rest, level[c])
      end
    end
    
    def longest_word(str)
      result, n = '', str.length
      n.times do |i|
        t = longest?(str[i..-1])
        result = t if t.size > result.size
        break if result.size > n-i # our micro optimization
      end
      result
    end
    
    def longest?(str, level = @trie)
      return '' if str.empty? or str.nil?
      
      c, rest = h_t(str)
  
      if level.has_key?(c)
        x = longest?(rest, level[c])
        if level[c].has_key?(:term) || !x.empty?
          c + x
        else
          ''
        end
      else
        ''
      end
    end
    
    def h_t(str)
      return str[0,1], str[1..-1]
    end
  end
  
  t = LameTrie.new(DICTIONARY)
  
  puts "Dictionary: #{DICTIONARY.inspect}"
  puts '[emptystring] -> ' + t.longest_word('')
  %w(a an antler crab crabapple pants polarbear adntsants oteuhbicyclentehut bearclaw).each do |str|
    puts str + ' -> ' + t.longest_word(str)
  end