Поиск подстроки в строке на go

Question

Поиск подстроки в строке на go

Рейтинг: 1Ответов: 1Опубликовано: 18.02.2023

Помогите,пожалуйста, напиать функцию поиска подстроки на go. Без лишних библиотек, и готовых функций. Просто поиск в чистом виде. На входе строка и подстрока, на выходе тру или фолс. Это решение, видимо не верное.

func findSubstring(str string, subStr string) bool {
    r := str
    sr := subStr
    if len(sr) == 0 {
        return false
    }
str:
    for i, ru := range r {
        if ru == sr[0] {
            for j, x := range sr[1:] {
                if r[i+j+1] != x {
                    continue str
                }
            }
            return true
        }
    }
    return false
}

golang substring

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

Если не гнаться за эффективностью, то алгоритм совсем простой - перебираете в исходной строке все подстроки нужной длины и сравниваете с заданной:

package main

import (
    "fmt"
)

func findSubstring(str string, match string) bool {
    if len(str) < len(match) {
        return false
    }
    for i := 0; i <= len(str)-len(match); i++ {
        subStr := str[i : i+len(match)]
        if subStr == match {
            return true
        }
    }
    return false
}

func main() {
    {
        s1, s2 := "Hello", "ll"
        fmt.Println(s1, s2, findSubstring(s1, s2))
    }
    {
        s1, s2 := "Hello", "world"
        fmt.Println(s1, s2, findSubstring(s1, s2))
    }
    {
        s1, s2 := "hello", "hello"
        fmt.Println(s1, s2, findSubstring(s1, s2))
    }
    {
        s1, s2 := "hello", "o"
        fmt.Println(s1, s2, findSubstring(s1, s2))
    }
    {
        s1, s2 := "hello", ""
        fmt.Println(s1, s2, findSubstring(s1, s2))
    }
}

Результат тут https://go.dev/play/p/1ywOePBrqEK

Это "наивная" реализация поиска. Есть заметно более продвинутые алгоритмы: Кнута-Морриса-Пратта и Бойера-Мура

Поиск подстроки в строке на go

Ответы