JetBrains Academy: Searching a substring in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki

JetBrains Academy: Searching a substring in Java

The first occurrence:

Given two strings, a pattern and a text. Write a program that prints the first index in which the pattern occurs in the text, or -1 if there are no occurrences.

NB: the empty string is a substring for any string.

import java.util.*;

public class Main {    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String pattern = scanner.nextLine();
        String text = scanner.nextLine();
        int firstOccurrence = Substring.findFirstOccurrence(pattern, text);
        
        System.out.println(firstOccurrence);
    }
}

class Substring {
    public static int findFirstOccurrence(String pattern, String text) {
        if (text.length() < pattern.length()) {
            return -1;
        }

        for (int i = 0; i < text.length() - pattern.length() + 1; i++) {
            boolean patternIsFound = true;

            for (int j = 0; j < pattern.length(); j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    patternIsFound = false;
                    break;
                }
            }

            if (patternIsFound) {
                return i;
            }
        }
        return -1;
    }
}

---

All occurrences:

Given two strings, a pattern and a text. Write a program that counts the number of times the pattern occurs in the text and prints indexes of all occurrences.

Input: two strings, a pattern and a text, each is on a separate line.

Output: the first line should contain the number of times the pattern occurs in the text. The second line should contain all indexes of occurrences separated by space.

Hint: an empty string is a substring for any string. The second test sample shows the output format in case a pattern is an empty string.

import java.util.*;

public class Main {    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String pattern = scanner.nextLine();
        String text = scanner.nextLine();
        Substring occurrences = Substring.findAllOccurrences(pattern, text);
        
        System.out.println(occurrences.toString());
    }
}

class Substring {
    public String indexes;
    public int count;

    public Substring(int count, String indexes) {
        this.count = count;
        this.indexes = indexes;
    }
    
    public static Substring findAllOccurrences(String pattern, String text) {
        int counter = 0;
        StringBuilder indexesB = new StringBuilder();

        if (text.length() < pattern.length()) {
            return new Substring(counter, "");
        }

        if (pattern.length() == 0) {
            return new Substring(1, "0");
        }

        for (int i = 0; i < text.length() - pattern.length() + 1; i++) {
            boolean patternIsFound = true;

            for (int j = 0; j < pattern.length(); j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    patternIsFound = false;
                    break;
                }
            }

            if (patternIsFound) {
                counter++;
                indexesB.append(i).append(" ");
            }
        }

        String indexes = indexesB.toString().trim();
        return new Substring(counter, indexes);
    }

    @Override
    public String toString() {
        return String.format("%d\n%s", count, indexes);
    }
}

---

Non-overlapping occurrences:

Let i and j are starting and ending indexes of a substring s in some string, i′ and j′ are starting and ending indexes of a substring s′ in the same string. s and s′ are called non-overlapping if i≤j<i′≤j′.

Given two strings, a pattern and a text. Write a program that finds all non-overlapping occurrences of the pattern in the text.

Input: two strings, a pattern and a text, each is on a separate line.

Output: the first line should contain the number of non-overlapping occurrences of the pattern in the text. The second line should contain all indexes of such occurrences separated by space. For two overlapping substrings, consider as occurrence the one that has the least starting index. If there are no occurrences output only one line with 0.

NB: the empty string is a substring for any string (see the second test case).

import java.util.*;

public class Main {    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String pattern = scanner.nextLine();
        String text = scanner.nextLine();
        Substring occurrences = Substring.findNonOverlappingOccurrences(pattern, text);
        
        System.out.println(occurrences.toString());
    }
}

class Substring {
    public String indexes;
    public int count;

    public Substring(int count, String indexes) {
        this.count = count;
        this.indexes = indexes;
    }
    
    public static Substring findNonOverlappingOccurrences(String pattern, String text) {
        int counter = 0;
        StringBuilder indexesB = new StringBuilder();

        if (text.length() < pattern.length()) {
            return new Substring(counter, "");
        }

        if (pattern.length() == 0) {
            return new Substring(1, "0");
        }

        for (int i = 0; i < text.length() - pattern.length() + 1; i++) {
            boolean patternIsFound = true;

            for (int j = 0; j < pattern.length(); j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    patternIsFound = false;
                    break;
                }
            }

            if (patternIsFound) {
                counter++;
                indexesB.append(i).append(" ");
                i += pattern.length() - 1;
            }
        }

        String indexes = indexesB.toString().trim();
        return new Substring(counter, indexes);
    }

    @Override
    public String toString() {
        return String.format("%d\n%s", count, indexes);
    }
}

---