# 检查一个字符串是否是另一个的子字符串

2021年3月12日15:08:32 发表评论 369 次浏览

## 本文概述

``````Input: s1 = "for", s2 = "lsbin"
Output: 5
Explanation:
String "for" is present as a substring
of s2.

Input: s1 = "practice", s2 = "lsbin"
Output: -1.
Explanation:
There is no occurrence of "practice" in
"lsbin"``````

## C ++

``````// CPP program to check if a string is
// substring of other.
#include <bits/stdc++.h>
using namespace std;

// Returns true if s1 is substring of s2
int 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;
}

/* Driver program to test above function */
int main()
{
string s1 = "for" ;
string s2 = "lsbin" ;
int res = isSubstring(s1, s2);
if (res == -1)
cout << "Not present" ;
else
cout << "Present at index " << res;
return 0;
}``````

## Java

``````// Java program to check if a string is
// substring of other.
class GFG {

// Returns true if s1 is substring of s2
static int 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.charAt(i + j)
!= s1.charAt(j))
break ;

if (j == M)
return i;
}

return - 1 ;
}

/* Driver program to test above function */
public static void main(String args[])
{
String s1 = "for" ;
String s2 = "lsbin" ;

int res = isSubstring(s1, s2);

if (res == - 1 )
System.out.println( "Not present" );
else
System.out.println(
"Present at index "
+ res);
}
}

// This code is contributed by JaideepPyne.``````

## Python 3

``````# Python 3 program to check if
# a string is substring of other.

# Returns true if s1 is substring of s2
def isSubstring(s1, s2):
M = len (s1)
N = len (s2)

# A loop to slide pat[] one by one
for i in range (N - M + 1 ):

# For current index i, # check for pattern match
for j in range (M):
if (s2[i + j] ! = s1[j]):
break

if j + 1 = = M :
return i

return - 1

# Driver Code
if __name__ = = "__main__" :
s1 = "for"
s2 = "lsbin"
res = isSubstring(s1, s2)
if res = = - 1 :
print ( "Not present" )
else :
print ( "Present at index " + str (res))

# This code is contributed by ChitraNayal``````

## C#

``````// C# program to check if a string is
// substring of other.
using System;
class GFG {

// Returns true if s1 is substring of s2
static int 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;
}

/* Driver program to test above function */
public static void Main()
{
string s1 = "for" ;
string s2 = "lsbin" ;

int res = isSubstring(s1, s2);

if (res == -1)
Console.Write( "Not present" );
else
Console.Write( "Present at index "
+ res);
}
}

// This code is contributed by nitin mittal.``````

## 的PHP

``````<?php
// PHP program to check if a
// string is substring of other.

// Returns true if s1 is substring of s2
function isSubstring( \$s1 , \$s2 )
{
\$M = strlen ( \$s1 );
\$N = strlen ( \$s2 );

// A loop to slide
// pat[] one by one
for ( \$i = 0; \$i <= \$N - \$M ; \$i ++)
{
\$j = 0;

// For current index i, // check for pattern match
for (; \$j < \$M ; \$j ++)
if ( \$s2 [ \$i + \$j ] != \$s1 [ \$j ])
break ;

if ( \$j == \$M )
return \$i ;
}

return -1;
}

// Driver Code
\$s1 = "for" ;
\$s2 = "lsbin" ;
\$res = isSubstring( \$s1 , \$s2 );
if ( \$res == -1)
echo "Not present" ;
else
echo "Present at index " . \$res ;

// This code is contributed by mits
?>``````

``Present at index 5``

• 时间复杂度：O(m * n), 其中m和n分别是s1和s2的长度。
使用嵌套循环, 外部循环从0到N-M, 内部循环从0到M, 因此复杂度为O(m * n)。
• 空间复杂度：O(1)。
由于不需要额外的空间。

An有效的解决方案是使用O(n)搜索算法, 例如KMP算法, Z算法等

• Java子串
• 用C ++代替
• Python查找