Dada una string grande y una serie de strings pequeñas, todas las cuales son más pequeñas que la string grande. La tarea es crear una array de booleanos, donde cada booleano representa si la string pequeña en ese índice en la array de strings pequeñas está contenida en la string grande. Nota: no puede usar métodos de coincidencia de strings incorporados en el idioma. Ejemplos:
Entrada: bigString = “esta es una string grande”, smallStrings = [“this”, “yo”, “is”, “a”, “más grande”, “string”, “kappa”] Salida: [verdadero, falso, true, true, false, true, false] Entrada: bigString = «Mary va al centro comercial todas las semanas»., smallStrings = [«to», «Mary», «centers», «shop», «shopping», » string”, “kappa”] Salida: [verdadero, verdadero, falso, verdadero, verdadero, falso, falso]
Enfoque: enfoque ingenuo Una forma simple de resolver este problema es iterar a través de todas las strings pequeñas, verificando si cada una de ellas está contenida en la string grande iterando a través de los caracteres de la string grande y comparándolos con los caracteres de la string pequeña dada con un par de bucles. A continuación se muestra la implementación del enfoque anterior:
C++
// Find the small string at that index in the array of
// small strings is contained in the big string
#include <bits/stdc++.h>
using namespace std;
bool isInBigString(string bigString, string smallString);
bool isInBigStringHelper(string bigString, string smallString, int startIdx);
// Function to the multiStringSearch
vector<bool> multiStringSearch(string bigString,
vector<string> smallStrings)
{
vector<bool> solution;
// iterate in the smallString
for (string smallString : smallStrings) {
// calling the isInBigString Function
solution.push_back(isInBigString(bigString, smallString));
}
return solution;
}
// Function to the bigString
bool isInBigString(string bigString, string smallString)
{
// iterate in the bigString
for (int i = 0; i < bigString.length(); i++) {
// Check if length of smallString + i is greater than
// the length of bigString
if (i + smallString.length() > bigString.length()) {
break;
}
// call the function isInBigStringHelper
if (isInBigStringHelper(bigString, smallString, i)) {
return true;
}
}
return false;
}
// Helper Function to the Finding bigString
bool isInBigStringHelper(string bigString, string smallString, int startIdx)
{
// Initialize leftBigIdx and rightBigIdx and leftSmallIdx variables
int leftBigIdx = startIdx;
int rightBigIdx = startIdx + smallString.length() - 1;
int leftSmallIdx = 0;
int rightSmallIdx = smallString.length() - 1;
// Iterate until leftBigIdx variable reaches less
// than or equal to rightBigIdx
while (leftBigIdx <= rightBigIdx) {
// Check if bigString[leftBigIdx] is not equal
// to smallString[leftSmallIdx] or Check if
// bigString[rightBigIdx] is not equal to
// smallString[rightSmallIdx] than return false
// otherwise increment leftBigIdx and leftSmallIdx
// decrement rightBigIdx and rightSmallIdx
if (bigString[leftBigIdx] != smallString[leftSmallIdx] ||
bigString[rightBigIdx] != smallString[rightSmallIdx]) {
return false;
}
leftBigIdx++;
rightBigIdx--;
leftSmallIdx++;
rightSmallIdx--;
}
return true;
}
// Driver code
int main(int argc, char* argv[])
{
// initialize string
string str = "this is a big string";
// initialize vector string
vector<string> substr = { "this", "yo", "is", "a",
"bigger", "string", "kappa" };
// Function call
vector<bool> ans = multiStringSearch(str, substr);
// Print answers
for (int i = 0; i < ans.size(); i++) {
// Check if ans[i] is equal to 1
// then Print true otherwise print false
if (ans[i] == 1) {
cout << "true"
<< " ";
}
else {
cout << "false"
<< " ";
}
}
return 0;
}
Python3
# Find the small string at that index in the array of
# small strings is contained in the big string
# Helper Function to the Finding bigString
def isInBigStringHelper(bigString,smallString,startIdx):
# Initialize leftBigIdx and rightBigIdx and leftSmallIdx variables
leftBigIdx = startIdx
rightBigIdx = startIdx + len(smallString) - 1
leftSmallIdx = 0
rightSmallIdx = len(smallString) - 1
# Iterate until leftBigIdx variable reaches less
# than or equal to rightBigIdx
while (leftBigIdx <= rightBigIdx):
# Check if bigString[leftBigIdx] is not equal
# to smallString[leftSmallIdx] or Check if
# bigString[rightBigIdx] is not equal to
# smallString[rightSmallIdx] than return false
# otherwise increment leftBigIdx and leftSmallIdx
# decrement rightBigIdx and rightSmallIdx
if (bigString[leftBigIdx] != smallString[leftSmallIdx] or
bigString[rightBigIdx] != smallString[rightSmallIdx]):
return False
leftBigIdx += 1
rightBigIdx -= 1
leftSmallIdx += 1
rightSmallIdx -= 1
return True
# Function to the bigString
def isInBigString(bigString, smallString):
# iterate in the bigString
for i in range(len(bigString)):
# Check if length of smallString + i is greater than
# the length of bigString
if (i + len(smallString) > len(bigString)):
break
# call the function isInBigStringHelper
if (isInBigStringHelper(bigString, smallString, i)):
return True
return False
# Function to the multiStringSearch
def multiStringSearch(bigString, smallStrings):
solution = []
# iterate in the smallString
for smallString in smallStrings:
# calling the isInBigString Function
solution.append(isInBigString(bigString, smallString))
return solution
# Driver code
if __name__ == '__main__':
# initialize string
str1 = "this is a big string"
# initialize vector string
substr = ["this", "yo", "is", "a","bigger", "string", "kappa"]
# Function call
ans = multiStringSearch(str1, substr)
# Print answers
for i in range(len(ans)):
# Check if ans[i] is equal to 1
# then Print true otherwise print false
if (ans[i] == 1):
print("true",end = " ")
else:
print("false",end = " ")
# This code is contributed by Bhupendra_Singh
Producción
true false true true false true false
Complejidad de tiempo: O(b * n * s), donde b es la longitud de la string grande y n es el número de strings pequeñas y s es la longitud de la string pequeña más larga. Espacio auxiliar: O(n) Enfoque: uso de Suffix Trie Cree una estructura de datos Suffix-trie que contenga todos los sufijos de la string grande. Luego, repita todas las strings pequeñas y verifique si cada una de ellas está contenida en la estructura de datos que ha creado. A continuación se muestra la implementación del enfoque anterior:
CPP
// Find the small string at that index in the array of
// small strings is contained in the big string
#include <bits/stdc++.h>
using namespace std;
// Blueprint of the TrieNode
class TrieNode {
public:
// Declaring children to be of <char, TrieNode> type
// key will be of char type and mapped value will
// be of TrieNode type
unordered_map<char, TrieNode*> children;
};
// Blueprint of the ModifiedSuffixTrie
class ModifiedSuffixTrie {
public:
TrieNode* root;
ModifiedSuffixTrie(string str)
{
this->root = new TrieNode();
// Function call
this->populateModifiedSuffixTrieFrom(str);
}
void populateModifiedSuffixTrieFrom(string str)
{
// iterate in the length of String
for (int i = 0; i < str.length(); i++) {
// Function call
this->insertSubstringStartingAt(i, str);
}
}
void insertSubstringStartingAt(int i, string str)
{
TrieNode* node = this->root;
// iterate in the length of String
for (int j = i; j < str.length(); j++) {
// initialize char as a letter
// put the value of str[j] in letter
char letter = str[j];
// Check if letter is is equal to endnode or not
if (node->children.find(letter) == node->children.end()) {
TrieNode* newNode = new TrieNode();
node->children.insert({ letter, newNode });
}
node = node->children[letter];
}
}
bool contains(string str)
{
TrieNode* node = this->root;
// iterate in the String
for (char letter : str) {
// Check if letter is is equal to endnode or not
if (node->children.find(letter) == node->children.end()) {
return false;
}
node = node->children[letter];
}
return true;
}
};
// Function to the multiStringSearch
vector<bool> multiStringSearch(string bigString, vector<string> smallStrings)
{
ModifiedSuffixTrie modifiedSuffixTrie(bigString);
vector<bool> solution;
// iterate in the smallString
for (string smallString : smallStrings) {
solution.push_back(modifiedSuffixTrie.contains(smallString));
}
return solution;
}
// Driver code
int main(int argc, char* argv[])
{
// initialize string
string str = "this is a big string";
// initialize vector string
vector<string> substr = { "this", "yo", "is", "a",
"bigger", "string", "kappa" };
// Function call
vector<bool> ans = multiStringSearch(str, substr);
// Print answers
for (int i = 0; i < ans.size(); i++) {
// Check if ans[i] is equal to 1
// then Print true otherwise print false
if (ans[i] == 1) {
cout << "true"
<< " ";
}
else {
cout << "false"
<< " ";
}
}
return 0;
}
Producción :
true false true true false true false
Complejidad de tiempo: O(b*b + n * s), donde b es la longitud de la string grande y n es el número de strings pequeñas y s es la longitud de la string pequeña más larga. Espacio auxiliar: O(b*2 + n) Enfoque: Uso de Trie Intente construir un trie que contenga todas las strings pequeñas. Luego, itere a través de los caracteres de la string grande y verifique si alguna parte de la string grande es una string contenida en el trie que ha creado. A continuación se muestra la implementación del enfoque anterior:
CPP
// Find the small string at that index in the array of
// small strings is contained in the big string
#include <bits/stdc++.h>
using namespace std;
// Blueprint of the TrieNode
class TrieNode {
public:
// Declaring children to be of <char, TrieNode> type
// key will be of char type and mapped value will
// be of TrieNode type
unordered_map<char, TrieNode*> children;
string word;
};
// Blueprint of the Trie
class Trie {
public:
TrieNode* root;
char endSymbol;
Trie()
{
this->root = new TrieNode();
this->endSymbol = '*';
}
// function to insert string
void insert(string str)
{
TrieNode* current = this->root;
// iterate in the length of String
for (int i = 0; i < str.length(); i++) {
// initialize char as a letter
// put the value of str[i] in letter
char letter = str[i];
// Check if letter is is equal to endnode or not
if (current->children.find(letter) == current->children.end()) {
TrieNode* newNode = new TrieNode();
current->children.insert({ letter, newNode });
}
current = current->children[letter];
}
current->children.insert({ this->endSymbol, NULL });
current->word = str;
}
};
// define a findSmallStringsIn function
void findSmallStringsIn(string str, int startIdx, Trie* trie,
unordered_map<string, bool>* containedStrings);
// Function to the multiStringSearch
vector<bool> multiStringSearch(string bigString, vector<string> smallStrings)
{
Trie* trie = new Trie();
// iterate in the smallString
for (string smallString : smallStrings) {
trie->insert(smallString);
}
// Declaring containedStrings to be of <string, bool> type
// key will be of string type and mapped value will
// be of boolean type
unordered_map<string, bool> containedStrings;
// iterate in the bigString
for (int i = 0; i < bigString.length(); i++) {
findSmallStringsIn(bigString, i, trie, &containedStrings);
}
vector<bool> solution;
// iterate in the smallString
for (string smallString : smallStrings) {
solution.push_back(containedStrings.find(smallString)
!= containedStrings.end());
}
return solution;
}
// Function to findSmallStringsIn
void findSmallStringsIn(string str, int startIdx,
Trie* trie, unordered_map<string, bool>* containedStrings)
{
TrieNode* currentNode = trie->root;
// iterate the length of the string
for (int i = startIdx; i < str.length(); i++) {
// Check if letter is is equal to endnode or not
if (currentNode->children.find(str[i]) ==
currentNode->children.end()) {
break;
}
currentNode = currentNode->children[str[i]];
if (currentNode->children.find(trie->endSymbol) !=
currentNode->children.end()) {
containedStrings->insert({ currentNode->word, true });
}
}
}
// Driver code
int main(int argc, char* argv[])
{
// initialize string
string str = "this is a big string";
// initialize vector string
vector<string> substr = { "this", "yo", "is", "a",
"bigger", "string", "kappa" };
// Function call
vector<bool> ans = multiStringSearch(str, substr);
// Print answers
for (int i = 0; i < ans.size(); i++) {
// Check if ans[i] is equal to 1
// then Print true otherwise print false
if (ans[i] == 1) {
cout << "true"
<< " ";
}
else {
cout << "false"
<< " ";
}
}
return 0;
}
Producción :
true false true true false true false
Complejidad de tiempo: O(n*s + b * s), donde b es la longitud de la string grande y n es el número de strings pequeñas y s es la longitud de la string pequeña más larga. Espacio Auxiliar : O(ns)
Enfoque Python3 usando el método find()
Python3
# python code to check whether a word is present in a string or not bigString = "this is a big string" smallStrings = ["this", "yo", "is", "a", "bigger", "string", "kappa"] x = [] # find() - returns position of specified value or else returns -1 for i in smallStrings: if(bigString.find(i) != -1): x.append(True) else: x.append(False) print(x)
Producción
[True, False, True, True, False, True, False]