Oct. 11, 2020, mock interview - find strings in given string - ideal solution is to use trie, build trie starting from all chars - 128

FindStringsInGivenString.cs

/*Given a string X and an array of small strings A, explain and implement an algorithm to search X for each small string in the array A.


How will you solve this problem if string X is a book of 5000 pages and the array has 1billion records?
10^10 * 5000 * 100^10 = 

26 English 
a, b, c, d, ... z  build a trie 26 -> more than unicode - 256, ascii - 128 
256 trees -> 

Example:
Given X = "mississippi"  and A[] =  {"is", "ppi", "hi", "sis", "I", "ssipi"}  <- those strings 
            --     ---                ---------------------------------------
            
            mississippi - > 
            -----------            
  trie
*/
        int[] findfirstPosition(string target, string[] searchable)    
        {
          var result = new int[searchable.Length]; 
          // 
          int index = 0; 
          foreach(var item in searchable)  
          {
            // item in target
            bool found = false;
            for(int i = 0; i + item.Length < target.Length; i++)
            {
              
              {
                   if(item.Substring(i, item.Length).CompareTo(target) == 0)
                   {
                    result[index] = i; 
                    found = true; 
                   }
              }
            }
            
            if(found == false)
            {
              result[index] = -1; 
            }
              
            index++;
          }
          
          return result; 
        }