Dada una string S de longitud N , la tarea es verificar si una string se puede dividir en dos substrings, digamos A y B , de modo que B sea una substring de A. Si no es posible , imprima No. De lo contrario, imprima Sí .
Ejemplos:
Entrada: S = “abcdab”
Salida: Sí
Explicación: Considerando que las dos divisiones son A=”abcd” y B=”ab”, B es una substring de A.Entrada: S = “abcd”
Salida: No
Enfoque ingenuo: el enfoque más simple para resolver el problema es dividir la string S en todos los índices posibles y verificar si la substring derecha es una substring de la substring izquierda . Si alguna división satisface la condición, imprima «Sí «. De lo contrario, escriba “No ”.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es verificar si el último carácter de la string S está presente en la string restante o no. Siga los pasos a continuación para resolver el problema:
- Almacene el último carácter de S en c .
- Compruebe si c está presente en la substring S[0, N-2] .
- Si es cierto, escriba «SÍ» . de lo contrario, escriba «NO» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a string can be
// divided into two substrings such that
// one substring is substring of the other
void splitString(string S, int N)
{
// Store the last character of S
char c = S[N - 1];
int f = 0;
// Traverse the characters at indices [0, N-2]
for (int i = 0; i < N - 1; i++) {
// Check if the current character is
// equal to the last character
if (S[i] == c) {
// If true, set f = 1
f = 1;
// Break out of the loop
break;
}
}
if (f)
cout << "Yes";
else
cout << "No";
}
// Driver Code
int main()
{
// Given string, S
string S = "abcdab";
// Store the size of S
int N = S.size();
// Function Call
splitString(S, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to check if a String can be
// divided into two subStrings such that
// one subString is subString of the other
static void splitString(String S, int N)
{
// Store the last character of S
char c = S.charAt(N - 1);
int f = 0;
// Traverse the characters at indices [0, N-2]
for (int i = 0; i < N - 1; i++)
{
// Check if the current character is
// equal to the last character
if (S.charAt(i) == c)
{
// If true, set f = 1
f = 1;
// Break out of the loop
break;
}
}
if (f > 0)
System.out.print("Yes");
else
System.out.print("No");
}
// Driver Code
public static void main(String[] args)
{
// Given String, S
String S = "abcdab";
// Store the size of S
int N = S.length();
// Function Call
splitString(S, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement
# the above approach
# Function to check if a can be
# divided into two substrings such that
# one subis subof the other
def splitString(S, N):
# Store the last character of S
c = S[N - 1]
f = 0
# Traverse the characters at indices [0, N-2]
for i in range(N - 1):
# Check if the current character is
# equal to the last character
if (S[i] == c):
# If true, set f = 1
f = 1
# Break out of the loop
break
if (f):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == '__main__':
# Given string, S
S = "abcdab"
# Store the size of S
N = len(S)
# Function Call
splitString(S, N)
# This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to check if a string can be
// divided into two substrings such that
// one substring is substring of the other
static void splitString(string S, int N)
{
// Store the last character of S
char c = S[N - 1];
int f = 0;
// Traverse the characters at indices [0, N-2]
for (int i = 0; i < N - 1; i++)
{
// Check if the current character is
// equal to the last character
if (S[i] == c)
{
// If true, set f = 1
f = 1;
// Break out of the loop
break;
}
}
if (f != 0)
Console.Write("Yes");
else
Console.Write("No");
}
// Driver code
public static void Main()
{
// Given string, S
string S = "abcdab";
// Store the size of S
int N = S.Length;
// Function Call
splitString(S, N);
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to check if a String can be
// divided into two subStrings such that
// one subString is subString of the other
function splitString(S , N)
{
// Store the last character of S
var c = S.charAt(N - 1);
var f = 0;
// Traverse the characters at indices [0, N-2]
for (var i = 0; i < N - 1; i++)
{
// Check if the current character is
// equal to the last character
if (S.charAt(i) == c)
{
// If true, set f = 1
f = 1;
// Break out of the loop
break;
}
}
if (f > 0)
document.write("Yes");
else
document.write("No");
}
// Driver Code
//Given String, S
var S = "abcdab";
// Store the size of S
var N = S.length;
// Function Call
splitString(S, N);
// This code contributed by shikhasingrajput
</script>
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)