Finds the position of a substring in another string if available.

FindFirstSubstring.swift

//: Playground - noun: a place where people can play

import Foundation

/*
Avoid using built-in functions to solve this challenge. Implement them yourself.
Implement a function that takes two strings, s and x, as arguments and finds the first occurrence of the string x in s. The function should return an integer indicating the index in s of the first occurrence of x. If there are no occurrences of x in s, return -1.

Example

For s = "CodefightsIsAwesome" and x = "IA", the output should be
strstr(s, x) = -1;
For s = "CodefightsIsAwesome" and x = "IsA", the output should be
strstr(s, x) = 10.
Input/Output

[time limit] 20000ms (swift)
[input] string s

A string containing only uppercase or lowercase English letters.

Guaranteed constraints:
1 ≤ s.length ≤ 106.

[input] string x

String, containing only uppercase or lowercase English letters.

Guaranteed constraints:
1 ≤ x.length ≤ 106.

[output] integer

An integer indicating the index of the first occurrence of the string x in s, or -1 if s does not contain x.
 
 
- Take grab substrings
 
 
 
*/

// This solution works, but is horribly slow with very large inputs.
// Best guess: Is that comparison of the entire substring is super inefficient with large inputs
func findFirstSubstringOccurrence_Slow(s: String, x: String) -> Int {
    
    // Check for valid inputs.
    guard s.count > 0 else { return -1 }
    guard x.count > 0 else { return -1 }
    
    // Check that the substring to be found is no
    // larger than the source string to comparing against.
    guard x.count <= s.count else { return -1 }
    
    // Iterate through the positions in
    // the source string.
    for i in 0..<s.count {
        
        // Check that we can still make
        // a full substring of the length of the
        // target. If not, we haven't found a
        // matching substring.
        if i + x.count > s.count {
            // Our target range "slice" is now out of
            // bounds of source string.
            // Could also return -1 here.
            break
        }
        
        let sourceSubstring = s[String.Index(encodedOffset: i)..<String.Index(encodedOffset: i + x.count)]
        
        if sourceSubstring == x {
            return i
        }
    }
    
    // Return here if we never found
    return -1
}


// Rather than comparing an entire string to some slice of another string,
// what if we looked at just the first character? If there is a match compare the next two characters
// and so on and so on until you have a full match of all the characters in the target string.
// We optimize away the full string comparison by only comparing the first few characters.
func findFirstSubstringOccurrence(s: String, x: String) -> Int {
    
    // Check for valid inputs.
    guard s.count > 0 else { return -1 }
    guard x.count > 0 else { return -1 }
    
    // Check that the substring to be found is no
    // larger than the source string to comparing against.
    guard x.count <= s.count else { return -1 }
    
    // Iterate through the positions in
    // the source string.
    for i in 0..<s.count {
        
        var outerChar = s[i]
        var outerCount = i;

        for j in 0..<x.count {
            
            let innerChar = x[j]
            
            print("Does \(outerChar) match \(innerChar)?")
            
            if outerChar == innerChar {
                //print("\(outerChar) matches \(innerChar)")
                
                if j == x.count - 1 {
                    // keep looping until an index "i" is found
                    // where all characters from i... to x.count match
                    
                    return i
                }
                
                // Check outer-count against
                outerCount += 1
                print("getting next char in s")
                outerChar = s[outerCount]
                
            } else {
                
                print("did not find match at index: \(i)")
                // no match, break from the inner loop
                break
            }
        }
    }
    
    // No match found
    return -1
}

// Extension for taking an Integer as a subscript value (because today its of type String.Index
// Returns the Character at that index.
extension String {
    subscript(i: Int) -> Character {
        return self[index(startIndex, offsetBy: i)]
    }
}


//
//findFirstSubstringOccurrence(s: "", x: "")
//findFirstSubstringOccurrence(s: "Something", x: "")
//findFirstSubstringOccurrence(s: "", x: "Something")
//findFirstSubstringOccurrence(s: "Code", x: "CodeIs")

//findFirstSubstringOccurrence(s: "CodefightsIsAwesome", x: "IA")

findFirstSubstringOccurrence(s: "CodefightsIsAwesome", x: "IsA")
findFirstSubstringOccurrence(s: "PIZZA", x: "IZZA")
findFirstSubstringOccurrence(s: "asdlfjo8781ljn,ba;lka;sldfkjbasldfjalkahvkhgiu87yiuhkjasbdfkjhhuhikka;lmxmnljbkajbsdf", x: "87yiuhkjasbdfk")
findFirstSubstringOccurrence(s: "asdlfjo8781ljn,ba;lka;sldfkjbasldfjalkahvkhgiu87yiuhkjasbdfkjhhuhikka;lmxmnljbkajbsdf", x: "87yiuhkjasbdfkjhhuhikka;lmxmnljbkajbsdfasdfasdfasdfaioiuoaidslfiasdknl1jbkuyiuy876817qtvjghvasdfjk,mnjbhjbiut7gavatvtcsjhvmcj1hvjhb1")
findFirstSubstringOccurrence(s: "ffbefbdbacbccecaceddcbcaeaebfedfcfdbeecffdbbf", x: "cb")