Show problems as
Classic problem #28EasyTwo PointersStringString MatchingZ AlgorithmKnuth–Morris–Pratt AlgorithmBoyer–Moore String-Search Algorithm

Find the Index of the First Occurrence in a String

Real-world version: Locate the Routing Tag
Tracked in this browser only
Read Find the Index of the First Occurrence in a String on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Every crate in a depot is stencilled with a long identifier, given as the lowercase string label. A conveyor belt decides where a crate goes by hunting for a short routing marker inside that identifier, given as the lowercase string tag.

Return the smallest index i such that the len(tag) consecutive characters of label starting at position i spell tag exactly. If the marker is nowhere inside the identifier, return -1.

Both strings are non-empty, and the marker may well be longer than the identifier.

Examples

Example 1

Input
label = "abracadabra", tag = "cad"
Output
4

Characters 4 through 6 of the identifier spell the marker; nothing earlier does.

Example 2

Input
label = "mississippi", tag = "issip"
Output
4

A shorter partial match begins at position 1 and dies at the fourth character, so the answer is the later position 4 where all five characters line up.

Example 3

Input
label = "banana", tag = "nab"
Output
-1

The three characters never sit next to each other in that arrangement.

Constraints

  • 1 <= label.length <= 10^4
  • 1 <= tag.length <= 10^4
  • label and tag contain only lowercase English letters

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def locate_tag(label: str, tag: str) -> int:
Java
public int locateTag(String label, String tag)

More on the same topics