Поиск подстрок - EcsFlash/DataTypes GitHub Wiki

Дана символьная строка длиной n называемая текстом и строка длиной m называемая шаблоном. Требуется найти в тексте подстроку соответствующую шаблону. То есть определить индекс i первого элемента подстроки в исходном тексте.

func FindSubstring(s string, sub string) int {
	for i := 0; i <= len(s)-len(sub); i++ {
		j := 0
		while j < len(sub) && sub[j] == s[i+j] {
			j++
		}
		if j == len(sub) {
			return i
		}
	}
	return -1
}

┌────────────┬───────────────┬────────────────┬──────────────┐
│ Сложность  │ Лучший случай │ Средний случай │ Худший случай│
├────────────┼───────────────┼────────────────┼──────────────┤
│   Время    │     O(m)      │     O(n*m)     │    O(n*m)    │
├────────────┼───────────────┼────────────────┼──────────────┤
│   Память   │     O(1)      │     O(1)       │    O(1)      │
└────────────┴───────────────┴────────────────┴──────────────┘

Анализ

Основная операция - сравнение