Check if a string is substring of another

Given two strings txt and pat, the task is to find if pat is a substring of txt. If yes, return the index of the first occurrence, else return -1.

Examples : 

Input: txt = "geeksforgeeks", pat = "eks"
Output: 2
Explanation: String "eks" is present at index 2 and 9, so 2 is the smallest index.

Input: txt = "geeksforgeeks", pat = "xyz"
Output: -1.
Explanation: There is no occurrence of "xyz" in "geeksforgeeks"

Using nested loops - O(m*n) Time and O(1) Space

The basic idea is to iterate through a loop in the string txt and for every index in the string txt, check whether we can match pat starting from this index. This can be done by running a nested loop for traversing the string pat and checking for each character of pat matches with txt or not. If all character of pat matches then return the starting index of such substring.

// C++ program to check if a string is substring of other // using nested loops #include <iostream> using namespace std; // Function to find if pat is a substring of txt int findSubstring(string &txt, string &pat) {  int n = txt.length();  int m = pat.length();  // Iterate through txt  for (int i = 0; i <= n - m; i++) {  // Check for substring match  int j;  for (j = 0; j < m; j++) {  // Mismatch found  if (txt[i + j] != pat[j]) {  break;  }  }  // If we completed the inner loop, we found a match  if (j == m) {  // Return starting index  return i;  }  }    // No match found  return -1; } int main() {  string txt = "geeksforgeeks";  string pat = "eks";  cout << findSubstring(txt, pat);  return 0; } 

// C program to check if a string is substring of other // using nested loops #include <stdio.h> #include <string.h> // Function to find if pat is a substring of txt int findSubstring(char *txt, char *pat) {  int n = strlen(txt);  int m = strlen(pat);  // Iterate through txt  for (int i = 0; i <= n - m; i++) {  // Check for substring match  int j;  for (j = 0; j < m; j++) {  // Mismatch found  if (txt[i + j] != pat[j]) {  break;  }  }  // If we completed the inner loop, we found a match  if (j == m) {  // Return starting index  return i;  }  }    // No match found  return -1; } int main() {  char txt[] = "geeksforgeeks";  char pat[] = "eks";  printf("%d", findSubstring(txt, pat));  return 0; } 

// Java program to check if a string is substring of other // using nested loops class GfG {    // Function to find if pat is a substring of txt  static int findSubstring(String txt, String pat) {  int n = txt.length();  int m = pat.length();  // Iterate through txt  for (int i = 0; i <= n - m; i++) {  // Check for substring match  int j;  for (j = 0; j < m; j++) {  // Mismatch found  if (txt.charAt(i + j) != pat.charAt(j)) {  break;  }  }  // If we completed the inner loop, we found a match  if (j == m) {  // Return starting index  return i;  }  }  // No match found  return -1;  }  public static void main(String[] args) {  String txt = "geeksforgeeks";  String pat = "eks";  System.out.println(findSubstring(txt, pat));  } } 

# Python program to check if a string is a substring of another # using nested loops # Function to find if pat is a substring of txt def findSubstring(txt, pat): n = len(txt) m = len(pat) # Iterate through txt for i in range(n - m + 1): # Check for substring match j = 0 while j < m and txt[i + j] == pat[j]: j += 1 # If we completed the inner loop, we found a match if j == m: return i # No match found return -1 if __name__ == "__main__": txt = "geeksforgeeks" pat = "eks" print(findSubstring(txt, pat)) 

// C# program to check if a string is substring of other // using nested loops using System; class GfG {    // Function to find if pat is a substring of txt  static int findSubstring(string txt, string pat) {  int n = txt.Length;  int m = pat.Length;  // Iterate through txt  for (int i = 0; i <= n - m; i++) {    // Check for substring match  int j;  for (j = 0; j < m; j++) {    // Mismatch found  if (txt[i + j] != pat[j]) {  break;  }  }  // If we completed the inner loop, we found a match  if (j == m) {    // Return starting index  return i;  }  }  // No match found  return -1;  }  static void Main() {  string txt = "geeksforgeeks";  string pat = "eks";  Console.WriteLine(findSubstring(txt, pat));  } } 

// JavaScript program to check if a string is a substring of another // using nested loops // Function to find if pat is a substring of txt function findSubstring(txt, pat) {  const n = txt.length;  const m = pat.length;  // Iterate through txt  for (let i = 0; i <= n - m; i++) {  // Check for substring match  let j;  for (j = 0; j < m; j++) {  // Mismatch found  if (txt[i + j] !== pat[j]) {  break;  }  }  // If we completed the inner loop, we found a match  if (j === m) {  // Return starting index  return i;  }  }  // No match found  return -1; } // Driver code const txt = "geeksforgeeks"; const pat = "eks"; console.log(findSubstring(txt, pat)); 

2

Time complexity: O(m * n) where m and n are lengths of txt and pat respectively. 
Auxiliary Space: O(1), as no extra space is required.

Using Pattern Searching Algorithms

There are several Pattern Searching Algorithms like KMP Algorithm, Rabin-Karp Algorithm, Aho-Corasick Algorithm, etc. Please refer to Introduction to Pattern Searching to learn more about them.

Using in-built library functions

This approach uses a built-in function to quickly check if pattern is part of text or not. This makes the process simple and efficient.

// C++ program to check if a string is substring of other // using in-built functions #include <iostream> using namespace std; int main() {  string txt = "geeksforgeeks";  string pat = "eks";    // If pat is found, returns the index of first  // occurrence of pat. Otherwise, returns a special  // constant value std::string::npos  size_t idx = txt.find(pat);    if(idx != string::npos)  cout << idx;  else  cout << -1;  return 0; } 

// C program to check if a string is substring of other // using in-built functions #include <stdio.h> #include <string.h> int main() {  const char *txt = "geeksforgeeks";  const char *pat = "eks";    // If pat is found, strstr returns a pointer to the first  // occurrence of pat in txt. Otherwise, it returns NULL.  const char *idx = strstr(txt, pat);    if (idx != NULL) {    // Calculate index by subtracting the base address   // of txt from result  printf("%ld", idx - txt);  }  else {  printf("-1");  }    return 0; } 

// Java program to check if a string is substring of other // using in-built functions class GfG {  public static void main(String[] args) {  String txt = "geeksforgeeks";  String pat = "eks";    // If pat is found, returns the index of first  // occurrence of pat. Otherwise, returns -1  int idx = txt.indexOf(pat);    if (idx != -1)  System.out.println(idx);  else  System.out.println(-1);  } } 

# Python program to check if a string is substring of other # using in-built functions if __name__ == "__main__": txt = "geeksforgeeks" pat = "eks" # If pat is found, returns the index of first # occurrence of pat. Otherwise, returns a special # constant value -1 idx = txt.find(pat) print(idx) 

// C# program to check if a string is substring of other // using in-built functions using System; class GfG {  static void Main() {  string txt = "geeksforgeeks";  string pat = "eks";    // If pat is found, returns the index of first  // occurrence of pat. Otherwise, returns a special  // constant value -1  int idx = txt.IndexOf(pat);    Console.WriteLine(idx);  } } 

// JavaScript program to check if a string is substring of other // using in-built functions let txt = "geeksforgeeks"; let pat = "eks"; // If pat is found, returns the index of first // occurrence of pat. Otherwise, returns -1 let idx = txt.indexOf(pat); console.log(idx); 

2

Note: The time complexity of in-built functions can differ across different languages.