import Foundation
// Non‑overlapping occurrences are matches of a substring that do not reuse any of
// the same characters. Once one match is counted, the next search must begin
// after that match ends.
func countNonOverlapping(haystack: String, needle: String) -> Int {
/*
Count how many times 'needle' appears in 'haystack' without overlapping.
The algorithm:
• Use str.find() to locate the next occurrence.
• Each time a match is found, move the search index forward
by the full length of the matched substring.
• This ensures no characters are reused between matches.
*/
// Handle edge case for empty needle to prevent infinite loop
if needle.isEmpty { return 0 }
var count = 0
var index = haystack.startIndex // current search position in the main string
// Continue searching until .find() returns -1 (meaning: no more matches)
while true {
// Find the next occurrence starting at the current index
if let range = haystack.range(of: needle, options: [], range: index..<haystack.endIndex) {
// We found a match, so increment the count
count += 1
// Move index forward by the length of the needle
// This ensures the next search begins *after* the matched substring
index = range.upperBound
} else {
// No more matches found
break
}
}
return count
}
// ---------------------------------------------------------------
// Demonstration using the string provided in the instructions:
let s = "go java phphp rust c pphpp c++ phpphp python php phphp"
let substring = "php"
// Count non-overlapping occurrences
let result = countNonOverlapping(haystack: s, needle: substring)
print("Non-overlapping occurrences: \(result)")
/*
run:
Non-overlapping occurrences: 6
*/
