Find a Substring (Naive Search)

easy Strings

Two words are given on two lines: a text and a pattern. Print the index (starting at 0) of the first place where the pattern appears in the text. Print -1 if it does not appear. Do not use a built-in search method.

Constraints

1 <= pattern length <= text length <= 2000

Examples

Input

hello
ll

Output

Nested loops
Pattern matching

Solutions

Brute forceTime O(n * m)Space O(1)

For each start position we compare the pattern with the text. The first full match gives the answer. In the worst case it needs n * m comparisons.

Same code works in Java810172125Basic features only, so nothing changes between versions.

/*
 * Problem : Search for a pattern.
 * Input   : Text and pattern.
 * Output  : The first index or -1.
 * Approach: Try every start position.
 * Time    : O(n * m)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(String a, String b) {
        // Step 1: Try every start position where the pattern can still fit.
        for (int start = 0; start + b.length() <= a.length(); start++) {
            // Step 2: Compare the pattern with the text, character by character.
            int offset = 0;
            while (offset < b.length() && a.charAt(start + offset) == b.charAt(offset)) {
                offset++;
            }

            // Step 3: If all characters of the pattern matched, we found it.
            if (offset == b.length()) {
                return start;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        String b = scanner.next();
        System.out.println(solve(a, b));
    }
}

Hints (1)

What is the last start position that can still match?