Print all occurrences of a string as a substring in another string

Given two strings, str1 and str2, the task is to print the indices(Consider, indices starting from 0) of the occurrence of str2 in str1. If no such index occurs, print “NONE”.

Examples:

Input : GeeksforGeeks
        Geeks
Output : 0 8
Input : GFG
        g
Output : NONE

Approach 1 (Naive Approach): 

A simple solution is to check all substrings of a given string one by one. If a substring matches print its index. 

Implementation:

// Java program to find indices of all
// occurrences of one String in other.
class GFG {

    static void printIndex(String str, String s)
    {

        boolean flag = false;
        for (int i = 0; i < str.length() - s.length() + 1;
             i++) {
            if (str.substring(i, i + s.length())
                    .equals(s)) {
                System.out.print(i + " ");
                flag = true;
            }
        }

        if (flag == false) {
            System.out.println("NONE");
        }
    }

    // Driver code
    public static void main(String[] args)
    {
        String str1 = "GeeksforGeeks";
        String str2 = "Geeks";
        printIndex(str1, str2);
    }
}

// This code is contributed by Rajput-JI

# Python program to find indices of all
# occurrences of one String in other.


def printIndex(str, s):

    flag = False
    for i in range(len(str)):
        if (str[i:i + len(s)] == s):

            print(i, end=" ")
            flag = True

    if (flag == False):
        print("NONE")


# Driver code
str1 = "GeeksforGeeks"
str2 = "Geeks"
printIndex(str1, str2)

# This code contributed by PrinciRaj1992

// C# program to find indices of all
// occurrences of one String in other.
using System;

class GFG {

    static void printIndex(String str, String s)
    {

        bool flag = false;
        for (int i = 0; i < str.Length - s.Length + 1;
             i++) {
            if (str.Substring(i, s.Length).Equals(s)) {
                Console.Write(i + " ");
                flag = true;
            }
        }

        if (flag == false) {
            Console.WriteLine("NONE");
        }
    }

    // Driver code
    public static void Main(String[] args)
    {
        String str1 = "GeeksforGeeks";
        String str2 = "Geeks";
        printIndex(str1, str2);
    }
}

// This code is contributed by 29AjayKumar

// JavaScript program to find indices of all
      // occurrences of one String in other.
      function printIndex(str, s) {
        var flag = false;
        for (var i = 0; i < str.length - s.length + 1; i++) {
          if (str.substring(i, s.length + i) == s) {
            console.log(i + " ");
            flag = true;
          }
        }
 
        if (flag === false) {
          console.log("NONE");
        }
      }
 
      // Driver code
      var str1 = "GeeksforGeeks";
      var str2 = "Geeks";
      printIndex(str1, str2);

<?php
// PHP program to find indices of all
// occurrences of one string in other.
function printIndex($str, $s)
{
    $flag = false;
    for ($i = 0; $i < strlen($str); $i++) 
    {
        if (substr($str,$i, strlen($s)) == $s)
        {
            echo $i . " ";
            $flag = true;
        }
    }

    if ($flag == false)
        echo "NONE";
}

// Driver Code
$str1 = "GeeksforGeeks";
$str2 = "Geeks";
printIndex($str1, $str2);

// This code is contributed by mits
?>

// C++ program to find indices of all
// occurrences of one string in other.
#include <iostream>
using namespace std;
void printIndex(string str, string s)
{

    bool flag = false;
    for (int i = 0; i < str.length(); i++) {
        if (str.substr(i, s.length()) == s) {
            cout << i << " ";
            flag = true;
        }
    }

    if (flag == false)
        cout << "NONE";
}
int main()
{
    string str1 = "GeeksforGeeks";
    string str2 = "Geeks";
    printIndex(str1, str2);
    return 0;
}

0 8 

Time Complexity: O(n * n)
Auxiliary Space: O(1), no extra space is required, so it is a constant.

Approach 2: (Using in-built STL functions)

This approach finds the first occurrence of the substring using find() with the starting position set to 0, and stores the index of the occurrence in the pos variable of type size_t. If the substring is not found, pos will be equal to string::npos, which is a static member constant with the maximum value for size_t, indicating that no occurrence was found. In this case, the function prints “NONE”.

If the substring is found, the function enters a while loop that prints the index of the first occurrence and then searches for subsequent occurrences using find() with the starting position set to the index of the previous occurrence plus one. This loop continues until no more occurrences are found, as indicated by pos being equal to string::npos.

Implementation:

1. Define the printIndex() function that takes two string arguments, str and s, representing the larger string and the substring to be searched, respectively. The function uses the find() function to find the first occurrence of the substring in the larger string, and then uses a while loop to find subsequent occurrences.
2. In the printIndex() function, if the substring is not found, the function prints “NONE” and returns.
3. In the printIndex() function, if the substring is found, the function prints the index of the first occurrence, and then continues searching for subsequent occurrences by calling find() again with the starting position of the search set to the index of the previous occurrence plus one.

// Java program to find indices of all
// occurrences of one string in other.

import java.util.*;

public class Main {
    public static void printIndex(String str, String s) {
        int pos = str.indexOf(s);

        if (pos == -1)
            System.out.println("NONE");

        while (pos != -1) {
            System.out.print(pos + " ");
            pos = str.indexOf(s, pos + 1);
        }
    }

    public static void main(String[] args) {
        String str1 = "GeeksforGeeks";
        String str2 = "Geeks";
        printIndex(str1, str2);
    }
}

def print_indices(s, sub):
    pos = s.find(sub)
    
    if pos == -1:
        print("NONE")
    
    while pos != -1:
        print(pos, end=" ")
        pos = s.find(sub, pos + 1)

if __name__ == "__main__":
    str1 = "GeeksforGeeks"
    str2 = "Geeks"
    print_indices(str1, str2)

// Function to print all occurrences of a substring in a string along with their indices
function printIndices(s, sub) {
    let pos = s.indexOf(sub); // Find the first occurrence of the substring
    let result = ""; // Initialize an empty string to store the indices
    
    if (pos === -1) { // If the substring is not found
        result = "NONE";
    } else {
        while (pos !== -1) { // Loop until all occurrences are found
            result += pos + " "; // Concatenate the index of the occurrence to the result string
            pos = s.indexOf(sub, pos + 1); // Find the next occurrence, starting from the next index
        }
    }
    console.log(result.trim()); // Print the result string, removing any trailing whitespace
}

// Main function
(function main() {
    const str1 = "GeeksforGeeks";
    const str2 = "Geeks";
    printIndices(str1, str2); // Call the printIndices function with the provided strings
})();

// C++ program to find indices of all
// occurrences of one string in other.
#include <bits/stdc++.h>
using namespace std;

void printIndex(string str, string s)
{

    size_t pos = str.find(s, 0);

    if (pos == string::npos)
        cout << "NONE";

    while (pos != string::npos) {
        cout << pos << " ";
        pos = str.find(s, pos + 1);
    }
}

// driver's code
int main()
{
    string str1 = "GeeksforGeeks";
    string str2 = "Geeks";
    printIndex(str1, str2);
    return 0;
}
// this code is contributed by prophet1999

0 8 

• The time complexity of the printIndex() function in the given code is O(n*m), where n is the length of the larger string and m is the length of the substring to be searched. This is because the function performs a find() operation for each character in the larger string, and in the worst case, the substring is found at every position. The find() operation itself has a time complexity of O(n), where n is the length of the string being searched, because it involves comparing each character in the string to the substring to be searched. Therefore, the overall time complexity of the program is O(n*m) in the worst case.
• The auxiliary space of the program is O(1) because it only uses a constant amount of memory to store the string variables and a few local variables used in the printIndex() function.

Approach 3: (Using two pointers)

The approach used is to iterate over the characters in the larger string and compare them with the characters in the substring. If a match is found, the index of the character in the larger string is printed, and the comparison continues with the next character in the substring. If a match is not found, the index in the larger string is reset to the previous match position plus one, and the comparison starts again from the beginning of the substring.

Implementation:

1. Initialize two integer variables, i and j, to 0. i represents the index of the current character in the substring being searched, and j represents the index of the current character in the larger string.
2. Declare a boolean variable flag and initialize it to false. This variable will be used to keep track of whether any occurrences of the substring were found.
3. Use a for loop to iterate over the characters in the larger string. At each iteration:
   • Compare the current character in the larger string with the current character in the substring. If they match, increment i to move to the next character in the substring.
   •  If i becomes equal to the length of the substring, that means a complete match has been found. Print the index of the first character of the match (which is j-i+1) to the console, set flag to true, and reset i to 0 to start searching for the next occurrence of the substring.
   • If the characters do not match, reset j to the previous match position plus one (which is j-i+1), set i to 0, and continue searching for the next occurrence of the substring.
4. After the for loop has finished, check whether any occurrences of the substring were found. If flag is still false, print “NONE” to the console.

public class Main {
    // Function to print indices of all occurrences of one string in another
    public static void printIndex(String str, String s) {
        int i = 0; // Initialize a pointer for the substring 's'
        boolean flag = false; // Initialize a flag to check if any occurrence is found

        for (int j = 0; j < str.length(); j++) {
            if (str.charAt(j) == s.charAt(i)) {
                i++; // If characters match, increment the pointer 'i'
            } else {
                j -= i; // If characters don't match, reset 'j' to its previous value
                i = 0; // Reset the pointer 'i'
            }
            
            if (i == s.length()) { // If the entire substring is found
                flag = true; // Set the flag to indicate an occurrence
                System.out.print(j - i + 1 + " "); // Print the starting index of the occurrence
            }
        }

        if (!flag) {
            System.out.print("NONE"); // If no occurrence is found, print "NONE"
        }
    }

    public static void main(String[] args) {
        String str1 = "GFG";
        String str2 = "g";
        printIndex(str1, str2);
    }
}

def print_index(string, substring):
    i = 0  # Initialize a pointer for the substring 'substring'
    flag = False  # Initialize a flag to check if any occurrence is found

    for j in range(len(string)):
        if string[j] == substring[i]:
            i += 1  # If characters match, increment the pointer 'i'
        else:
            j -= i  # If characters don't match, reset 'j' to its previous value
            i = 0  # Reset the pointer 'i'

        if i == len(substring):  # If the entire substring is found
            flag = True  # Set the flag to indicate an occurrence
            print(j - i + 1, end=" ")  # Print the starting index of the occurrence

    if not flag:
        print("NONE", end="")  # If no occurrence is found, print "NONE"


if __name__ == "__main__":
    str1 = "GFG"
    str2 = "g"
    print_index(str1, str2)

function printIndex(str, s) {
    let i = 0; // Initialize a pointer for the substring 's'
    let flag = false; // Initialize a flag to check if any occurrence is found

    for (let j = 0; j < str.length; j++) {
        if (str.charAt(j) === s.charAt(i)) {
            i++; // If characters match, increment the pointer 'i'
        } else {
            j -= i; // If characters don't match, reset 'j' to its previous value
            i = 0; // Reset the pointer 'i'
        }

        if (i === s.length) { // If the entire substring is found
            flag = true; // Set the flag to indicate an occurrence
            process.stdout.write((j - i + 1) + ' '); // Print the starting index of the occurrence
        }
    }

    if (!flag) {
        process.stdout.write("NONE"); // If no occurrence is found, print "NONE"
    }
}

// Example usage:
const str1 = "GFG";
const str2 = "g";
printIndex(str1, str2);

// C++ program to find indices of all
// occurrences of one string in other.
#include <bits/stdc++.h>
using namespace std;

void printIndex(string str, string s)
{

    int i = 0;
    bool flag = 0;

    for (int j = 0; j < str.length(); j++) {
        if (str[j] == s[i])
            i++;
        else {
            j -= i;
            i = 0;
        }
        if (i == s.length()) {
            flag = 1;
            cout << j - i + 1 << " ";
        }
    }

    if (!flag)
        cout << "NONE";
}

// driver's code
int main()
{
    string str1 = "GFG";
    string str2 = "g";
    printIndex(str1, str2);
    return 0;
}
// this code is contributed by prophet1999

NONE

• The time complexity of the printIndex() function in the given code is O(n*m), where n is the length of the larger string and m is the length of the substring to be searched. In the worst case, every character in the larger string needs to be checked for a match with the first character of the substring, resulting in n iterations of the for loop. In addition, for each matching character in the larger string, the function also needs to check the next m-1 characters to see if a complete match has been found. Therefore, the worst-case time complexity of the function is O(n*m).
• The auxiliary space of the function is O(1), since the function only uses a few integer and boolean variables to keep track of the current state of the search.

An efficient solution is to KMP string matching algorithm