Easy Way to Check if C String Has Substring
Check if a string is substring of another
Given two strings s1 and s2, find if s1 is a substring of s2. If yes, return the index of the first occurrence, else return -1.
Examples :
Input: s1 = "for", s2 = "geeksforgeeks"
Output: 5
Explanation: String "for" is present as a substring of s2.Input: s1 = "practice", s2 = "geeksforgeeks"
Output: -1.
Explanation: There is no occurrence of "practice" in "geeksforgeeks"
Simple Approach:
The idea is to run a loop from start to end and for every index in the given string check whether the sub-string can be formed from that index. This can be done by running a nested loop traversing the given string and in that loop running another loop checking for sub-string from every index.
For example, consider there to be a string of length N and a substring of length M. Then run a nested loop, where the outer loop runs from 0 to (N-M) and the inner loop from 0 to M. For very index check if the sub-string traversed by the inner loop is the given sub-string or not.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
int isSubstring(string s1, string s2)
{
int M = s1.length();
int N = s2.length();
for ( int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++)
if (s2[i + j] != s1[j])
break ;
if (j == M)
return i;
}
return -1;
}
int main()
{
string s1 = "for" ;
string s2 = "geeksforgeeks" ;
int res = isSubstring(s1, s2);
if (res == -1)
cout << "Not present" ;
else
cout << "Present at index " << res;
return 0;
}
Java
class GFG {
static int isSubstring(
String s1, String s2)
{
int M = s1.length();
int N = s2.length();
for ( int i = 0 ; i <= N - M; i++) {
int j;
for (j = 0 ; j < M; j++)
if (s2.charAt(i + j)
!= s1.charAt(j))
break ;
if (j == M)
return i;
}
return - 1 ;
}
public static void main(String args[])
{
String s1 = "for" ;
String s2 = "geeksforgeeks" ;
int res = isSubstring(s1, s2);
if (res == - 1 )
System.out.println( "Not present" );
else
System.out.println(
"Present at index "
+ res);
}
}
Python3
def isSubstring(s1, s2):
M = len (s1)
N = len (s2)
for i in range (N - M + 1 ):
for j in range (M):
if (s2[i + j] ! = s1[j]):
break
if j + 1 = = M :
return i
return - 1
if __name__ = = "__main__" :
s1 = "for"
s2 = "geeksforgeeks"
res = isSubstring(s1, s2)
if res = = - 1 :
print ( "Not present" )
else :
print ( "Present at index " + str (res))
C#
using System;
class GFG {
static int isSubstring( string s1, string s2)
{
int M = s1.Length;
int N = s2.Length;
for ( int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++)
if (s2[i + j] != s1[j])
break ;
if (j == M)
return i;
}
return -1;
}
public static void Main()
{
string s1 = "for" ;
string s2 = "geeksforgeeks" ;
int res = isSubstring(s1, s2);
if (res == -1)
Console.Write( "Not present" );
else
Console.Write( "Present at index "
+ res);
}
}
PHP
<?php
function isSubstring( $s1 , $s2 )
{
$M = strlen ( $s1 );
$N = strlen ( $s2 );
for ( $i = 0; $i <= $N - $M ; $i ++)
{
$j = 0;
for (; $j < $M ; $j ++)
if ( $s2 [ $i + $j ] != $s1 [ $j ])
break ;
if ( $j == $M )
return $i ;
}
return -1;
}
$s1 = "for" ;
$s2 = "geeksforgeeks" ;
$res = isSubstring( $s1 , $s2 );
if ( $res == -1)
echo "Not present" ;
else
echo "Present at index " . $res ;
?>
Javascript
<script>
function isSubstring(s1, s2)
{
var M = s1.length;
var N = s2.length;
for ( var i = 0; i <= N - M; i++) {
var j;
for (j = 0; j < M; j++)
if (s2[i + j] != s1[j])
break ;
if (j == M)
return i;
}
return -1;
}
var s1 = "for" ;
var s2 = "geeksforgeeks" ;
var res = isSubstring(s1, s2);
if (res == -1)
document.write( "Not present" );
else
document.write( "Present at index " + res);
</script>
Complexity Analysis:
- Time complexity: O(m * n) where m and n are lengths of s1 and s2 respectively.
A nested loop is used the outer loop runs from 0 to N-M and the inner loop from 0 to M so the complexity is O(m*n). - Space Complexity: O(1).
As no extra space is required.
An efficient solution is to use a O(n) searching algorithm like KMP algorithm, Z algorithm, etc.
Language implementations:
- Java Substring
- substr in C++
- Python find
Another Efficient Solution:
- An efficient solution would need only one traversal i.e. O(n) on the longer string s1. Here we will start traversing the string s1 and maintain a pointer for string s2 from 0th index.
- For each iteration, we compare the current character in s1 and check it with the pointer at s2.
- If they match we increment the pointer on s2 by 1. And for every mismatch, we set the pointer back to 0.
- Also keep a check when the s2 pointer value is equal to the length of string s2, if true we break and return the value (pointer of string s1 – pointer of string s2)
- Works with strings containing duplicate characters.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
int Substr(string s2, string s1)
{
int counter = 0;
int i = 0;
for (;i<s1.length();i++)
{
if (counter==s2.length())
break ;
if (s2[counter]==s1[i])
{
counter++;
}
else
{
if (counter > 0)
{
i -= counter;
}
counter = 0;
}
}
return counter < s2.length()?-1:i-counter;
}
int main()
{
string s1 = "geeksforgeeks" ;
cout << Substr( "for" , s1);
return 0;
}
Java
import java.io.*;
class GFG {
public static int Substr(String s2, String s1){
int counter = 0 ;
int i = 0 ;
for (;i<s1.length();i++){
if (counter==s2.length())
break ;
if (s2.charAt(counter)==s1.charAt(i)){
counter++;
} else {
if (counter> 0 ){
i -= counter;
}
counter = 0 ;
}
}
return counter < s2.length()?- 1 :i-counter;
}
public static void main (String[] args) {
String s1 = "geeksforgeeks" ;
System.out.println(Substr( "for" , s1));
}
}
Python3
def Substr(s1, s2):
counter = 0
i = 0
Len = len (s1)
while (i < Len ):
if (counter = = len (s2)):
break ;
if (s2[counter] = = s1[i]):
counter + = 1
else :
if (counter > 0 ):
i - = counter
counter = 0
i + = 1
if (counter < len (s2)):
return - 1
else :
return (i - counter)
print (Substr( "geeksforgeeks" , "for" ))
C#
using System;
class GFG {
static int Substr( string s2, string s1)
{
int counter = 0;
int i = 0;
for (; i < s1.Length; i++) {
if (counter == s2.Length)
break ;
if (s2[counter] == s1[i]) {
counter++;
}
else {
if (counter > 0) {
i -= counter;
}
counter = 0;
}
}
return counter < s2.Length ? -1 : i - counter;
}
public static int Main()
{
string s1 = "geeksforgeeks" ;
Console.Write(Substr( "for" , s1));
return 0;
}
}
Javascript
<!-- Javascript program for the above approach -->
<script>
function Substr( s2, s1){
var counter = 0;
var i = 0;
for ( ;i < s1.length; i++)
{
if ( counter == s2.length )
{
break ;
}
if ( s2[counter] == s1[i] )
{
counter++;
}
else
{
if (counter > 0)
{
i -= counter;
}
counter = 0;
}
}
return counter < s2.length ? -1 : i-counter;
}
var s1 = "geeksforgeeks" ;
document.write(Substr( "for" , s1));
</script>
<!-- this code is contributed by Nirajgusain5 -->
Complexity Analysis:a
- Time Complexity: O(n*m) in the worst case
- Auxiliary complexity: O(1).
Using Library Methods
Modern programming languages typically have inbuilt library methods that check if one string is present in another, and the index at which it is located. For instance, the std::find from C++ STL, the index method in Python, the indexOf method in Java, the indexOf method in JavaScript.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
int isSubstring(string s1, string s2)
{
if (s2.find(s1) != string::npos)
return s2.find(s1);
return -1;
}
int main()
{
string s1 = "for" ;
string s2 = "geeksforgeeks" ;
int res = isSubstring(s1, s2);
if (res == -1)
cout << "Not present" ;
else
cout << "Present at index " << res;
return 0;
}
Python3
def isSubstring(s1, s2):
if s1 in s2:
return s2.index(s1)
return - 1
if __name__ = = "__main__" :
s1 = "for"
s2 = "geeksforgeeks"
res = isSubstring(s1, s2)
if res = = - 1 :
print ( "Not present" )
else :
print ( "Present at index " + str (res))
Java
class GFG {
static int isSubstring(String s1, String s2)
{
return s2.indexOf(s1);
}
public static void main(String[] args) {
String s1 = "for" ;
String s2 = "geeksforgeeks" ;
int res = isSubstring(s1, s2);
if (res == - 1 )
System.out.println( "Not present" );
else
System.out.println( "Present at index " + res);
}
}
Javascript
function isSubstring(s1, s2)
{
return s2.indexOf(s1);
}
var s1 = "for" ;
var s2 = "geeksforgeeks" ;
var res = isSubstring(s1, s2);
if (res == -1)
console.log( "Not present" );
else
console.log( "Present at index " + res);
C#
using System;
public class GFG {
static int isSubstring( string s1, string s2)
{
return s2.IndexOf(s1);
}
public static void Main( string [] args)
{
string s1 = "for" ;
string s2 = "geeksforgeeks" ;
int res = isSubstring(s1, s2);
if (res == -1)
Console.WriteLine( "Not present" );
else
Console.WriteLine( "Present at index " + res);
}
}
Source: https://www.geeksforgeeks.org/check-string-substring-another/
0 Response to "Easy Way to Check if C String Has Substring"
Enregistrer un commentaire