0

According this answer (Find all possible substring in fastest way). The fastest way to find all possible substrings of a String is O(N^2). However, is this still true if let's say I have a list of words, and I wan't to see if a certain string x has substrings that are in that list of words. For instance, would creating a trie of the list of words, allow me to optimally ignore certain substrings. Thus making the run time better?

carlosdafield
  • 1,479
  • 5
  • 16
  • Checking if a string (word) is a substring of a larger string is linear. Checking for K words is still linear. – zerkms Jan 25 '22 at 02:08

1 Answers1

1

Yes, that is what string searching algorithms are for.

enter image description here

Shridhar R Kulkarni
  • 6,653
  • 3
  • 37
  • 57