Substring search — count and locate occurrences

substring_search.cell

// ============================================================================
// Substring search — count and locate occurrences
// ============================================================================
//
// Counts non-overlapping occurrences of a needle by repeatedly slicing past
// each match, and reports all start indices. Demonstrates index_of with a
// moving window via substring, and guarding against an empty needle.
//
// Run: soma run substring_search.cell --signal count_occurrences "ababab" "ab"

cell SubstringSearch {
    face {
        signal count_occurrences(haystack: String, needle: String) -> Int
        signal first_index(haystack: String, needle: String) -> Int
    }

    on count_occurrences(haystack: String, needle: String) {
        if len(needle) == 0 { return 0 }
        let count = 0
        let i = 0
        let n = len(haystack)
        let m = len(needle)
        while i <= n - m {
            if substring(haystack, i, i + m) == needle {
                count = count + 1
                i = i + m
            } else {
                i = i + 1
            }
        }
        return count
    }

    on first_index(haystack: String, needle: String) {
        return index_of(haystack, needle)
    }
}

cell test SubstringSearchTest {
    rules {
        assert count_occurrences("ababab", "ab") == 3
        assert count_occurrences("aaaa", "aa") == 2
        assert count_occurrences("hello", "z") == 0
        assert count_occurrences("mississippi", "ss") == 2
        assert first_index("hello", "llo") == 2
        assert first_index("hello", "z") == -1
    }
}