Given an array of string arr[] and a string str, the task is to print all the strings in arr[] that occur as a substring in str.
Example:
Input: str =”neveropen”, arr[] ={ “forg”, “geek”, “ek”, “dog”, “sfor”}
Output:
forg
geek
ek
sfor
Explanation: The strings “forg”, “geek”, “ek” and “sfor” occur as a substring in str. Therefore, the required count is 4.Input: str =”abcd”, arr[] ={ “aa”, “bb”, “cc”}
Output: -1
Approach: The given problem is an implementation base problem. It can be solved by iterating over the given array of strings and for each string in arr[], check whether it occurs as a substring of str or not using the algorithm discussed in this article. Maintain a variable that stores If no string exists as a substring. In that case, print -1.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Returns true if s1 is substring of s2int isSubstring(string s1, string s2){ int M = s1.length(); int N = s2.length(); /* A loop to slide pat[] one by one */ for (int i = 0; i <= N - M; i++) { int j; /* For current index i, check for pattern match */ for (j = 0; j < M; j++) if (s2[i + j] != s1[j]) break; if (j == M) return i; } return -1;}// Function to print all the strings// in the given array that occur as// the substring in the given stringvoid isSubstr(string Str, string arr[], int len){ // Stores if no string is a // substring of str int flag = 0; // Iterate over the array of strings for (int i = 0; i < len; i++) { // if the current string occur // as a substring in Str int s = isSubstring(arr[i],Str); if (s != -1) { // Print string i cout << arr[i] <<endl; flag = 1; } } // If no substring exist if (flag == 0) cout<<"-1"<<endl;}// Driver Codeint main(){ string arr[5] = { "forg", "geek", "ek", "dog", "sfo"}; int len = sizeof(arr)/sizeof(arr[0]); string Str = "neveropen"; isSubstr(Str, arr, len); return 0;}// This code is contributed by sanjoy_62. |
Java
// JAVA program of the above approachimport java.util.*;class GFG{ // Function to print all the strings // in the given array that occur as // the substring in the given string public static void isSubstr(String Str, ArrayList<String> arr) { // Stores if no string is a // substring of str int flag = 0; // Iterate over the array of strings for (int i = 0; i < arr.size(); i++) { // if the current string occur // as a substring in Str if (Str.indexOf(arr.get(i)) != -1) { // Print string i System.out.println(arr.get(i)); flag = 1; } } // If no substring exist if (flag == 0) System.out.print(-1); } // Driver Code public static void main(String[] args) { ArrayList<String> arr = new ArrayList<>(Arrays.asList( "forg", "geek", "ek", "dog", "sfo")); String Str = "neveropen"; isSubstr(Str, arr); }}// This code is contributed by Taranpreet |
Python3
# Python program of the above approach# Function to print all the strings# in the given array that occur as# the substring in the given stringdef isSubstr(Str, arr): # Stores if no string is a # substring of str flag = 0 # Iterate over the array of strings for i in arr: # if the current string occur # as a substring in Str if i in Str: # Print string i print(i) flag = 1 # If no substring exist if flag == 0: print(-1)# Driver Codearr = ["forg", "geek", "ek", "dog", "sfo"]Str = "neveropen"isSubstr(Str, arr) |
C#
// C# program of the above approachusing System;public class GFG{ // Function to print all the strings // in the given array that occur as // the substring in the given string public static void isSubstr(String Str,String[] arr) { // Stores if no string is a // substring of str int flag = 0; // Iterate over the array of strings for (int i = 0; i < arr.Length; i++) { // if the current string occur // as a substring in Str if (Str.IndexOf(arr[i]) != -1) { // Print string i Console.WriteLine(arr[i]); flag = 1; } } // If no substring exist if (flag == 0) Console.Write(-1); } // Driver Code public static void Main(String[] args) { String[] arr = {"forg", "geek", "ek", "dog", "sfo"}; String Str = "neveropen"; isSubstr(Str, arr); }}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program of the above approach // Function to print all the strings // in the given array that occur as // the substring in the given string const isSubstr = (Str, arr) => { // Stores if no string is a // substring of str let flag = 0; // Iterate over the array of strings for (i in arr) { // if the current string occur // as a substring in Str if (Str.indexOf(arr[i]) != -1) { // Print string i document.write(`${arr[i]}<br/>`); flag = 1; } } // If no substring exist if (flag == 0) document.write(-1); } // Driver Code let arr = ["forg", "geek", "ek", "dog", "sfo"]; let Str = "neveropen"; isSubstr(Str, arr) // This code is contributed by rakeshsahni</script> |
Output
forg geek ek sfo
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
