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

本文概述

给定两个字符串s1和s2, 请确定s1是否为s2的子字符串。如果是, 则返回第一次出现的索引, 否则返回-1。

例子 ：

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"

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

简单方法：

这个想法是从头到尾运行一个循环, 对于给定字符串中的每个索引, 检查是否可以从该索引中形成子字符串。这可以通过运行遍历给定字符串的嵌套循环并在该循环中运行另一个循环来检查每个索引中的子字符串来完成。

例如,

假设有一个长度为N的字符串和一个长度为M的子字符串。然后运行一个嵌套循环, 其中外循环从0到(NM), 内循环从0到M。内循环遍历的字符串是否为给定的子字符串。

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查找

---