String::npos in C++
In this article, you will learn about the string::npos in C++ with several examples.
Introduction:
The std::string::npos is defined as a constant value that represents the largest possible value that can be held by the std::string::size_type type. The size_type type is an unsigned integral type that is used to represent sizes and indices within a std::string. By convention, std::string::npos is used to signify that a specific position or index within a string is not found or is invalid. It is particularly useful when you're searching for substrings or characters within a string and need to check if the search was unsuccessful.
Program:
Here's a code shown below demonstrates the usage of std::string::npos in C++:
#include <iostream>
#include <string>
int main() {
std::string text = "Hello, World!";
std::string searchString = "Java";
// Find the position of "Java" in the text
size_t found = text.find(searchString);
if (found != std::string::npos) {
// "Java" is found in the text
std::cout << "Found at position: " << found << std::endl;
} else {
// "Java" is not found in the text
std::cout << "Not found in the text." << std::endl;
}
return 0;
}
Output:
Not found in the text.
Explanation:
- #include Directives:
The code begins with two #include directives. These directives are used to include necessary header files for input and output (<iostream>) and for working with strings (<string>). These headers provide the necessary functionality for our program.
- int main():
It is the entry point of the C++ program. All C++ programs start execution from the main function.
- Variable Declarations:
std::string text = "Hello, World!";: Here, a string variable named text is declared and initialized with the text "Hello, World!". It is the text where we'll search for another substring in.
std::string searchString = "Java";: Another string variable named searchString is declared and initialized with the text "Java". It is the substring where we want to search for in the text string.
- Searching for a Substring:
size_t found = text.find(searchString);: The find method is used on the text string to search for the position of the searchString within it. The result of this search (i.e., the index where the substring is found) is stored in the found variable, which is of type size_t.
- Conditional Check:
If (found != std::string::npos): This line checks if the value stored in found is not equal to std::string::npos. If found is not equal to std::string::npos, it means that the searchString was found in the text string. In this case, the code inside the if block will be executed.
- Output When Substring is Found:
std::cout << "Found at position: " << found << std::endl;: If the searchString is found, this line prints a message indicating that the substring was found and displays the position (index) where it was found within the text string.
- Output When Substring is Not Found:
If the searchString is not found (i.e., found == std::string::npos), the code inside the else block is executed:
std::cout << "Not found in the text." << std::endl;: This line prints a message indicating that the substring was not found in the text string.
- Program Termination:
return 0;: This line is used to indicate that the program has executed without errors and returns a status code of 0 to the operating system.
Complexity analysis:
Time Complexity:
- String Initialization:
Initializing the text and searchString strings takes O(1) time as the lengths of the strings are constant.
- text.find(searchString):
The time complexity of the find method for strings is O(N*M), where N is the length of the text string, and M is the length of the searchString.
In this case, the text string has a length of 13 characters ("Hello, World!"), and the searchString has a length of 4 characters ("Java"). So, the time complexity of this operation is O(13*4) = O(52).
- Conditional Check and Output:
The conditional check and output statements are O(1) operations. They do not depend on the length of the strings.
Overall, the time complexity of this code is dominated by the find operation, which is O(N*M) in the worst case.
Space Complexity:
- String Variables:
In this example, the std::string text and std::string searchString are string variables. The space they consume is proportional to the lengths of the strings they hold.
In this case, the space used by these string variables is O(13 + 4) = O(17) because "Hello, World!" has 13 characters, and "Java" has 4 characters.
- size_t found:
size_t found is a single variable that stores the position where the searchString is found. It does not depend on the length of the strings.
So, the space complexity for size_t found is O(1).
Approach 2: Using std::string::find() with a Loop
Program:
Here's a code shown below demonstrates the usage of std::string::find with a loop in C++:
#include <iostream>
#include <string>
int main() {
std::string text = "Hello, World!";
std::string searchString = "Java";
size_t found = text.find(searchString); // Search for the first occurrence of searchString
size_t position = 0; // Initialize the starting position
while (found != std::string::npos) { // Continue searching until no more occurrences are found
std::cout << "Found at position: " << position + found << std::endl; // Print the position of the found substring
position += found + 1; // Move the position to the next character after the found occurrence
found = text.find(searchString, position); // Search for the next occurrence
}
if (position == 0) { // If no occurrences were found, the position remains at its initial value
std::cout << "Not found in the text." << std::endl;
}
return 0;
}
Output:
Not found in the text.
Explanation:
- #include Directives:
In this example, the code begins with two #include directives to include necessary header files for input and output (<iostream>) and for working with strings (<string>). These headers provide the necessary functionality for the program.
- Variable Declarations:
std::string text = "Hello, World!";: This line declares and initializes a string variable named text with the value "Hello, World!".
std::string searchString = "Java";: Another string variable, searchString, is declared and initialized with the value "Java". It is the substring where we want to search for in text.
- Searching for the Substring:
size_t found = text.find(searchString);: The find method is used to search for the first occurrence of searchString within the text string. The result of this search (the index where the substring is found) is stored in the found variable, which is of type size_t.
- Initialize Position:
size_t position = 0;: The position variable is used to keep track of the starting position for the next search. It is initialized to 0, indicating that we start searching from the beginning of the text.
- While Loop for Multiple Occurrences:
while (found != std::string::npos) {: This while loop continues as long as found is not equal to std::string::npos. It means the loop continues as long as the substring is found within the text.
std::cout << "Found at position: " << position + found << std::endl;: Inside the loop, we print the position where the substring was found. We add position to the found function to get the absolute position within the entire text.
position += found + 1;: We update the position to start searching for the next occurrence. We add found (the index of the current occurrence) and 1 to ensure we start after the current occurrence.
found = text.find(searchString, position);: We search for the next occurrence of searchString starting from the updated position. The result is stored in found.
Check for No Occurrences:
If (position == 0) {: After the loop, we check if the position is still at its initial value. If it is, it means that no occurrences of searchString were found in the text.
std::cout << "Not found in the text." << std::endl;: In this case, we print a message indicating that the substring was not found in the text.
- Program Termination:
return 0;: This line indicates that the program has executed without errors and returns a status code of 0 to the operating system.
Complexity analysis:
Time Complexity:
The time complexity of this code is dominated by the find method. The worst-case time complexity of the find method is O(N*M), where N is the length of the text string, and M is the length of the searchString. In this case, it may involve multiple iterations over the text string to find all occurrences.
Space Complexity:
The space complexity is determined by the space used for the string variables and is O(N + M), where N is the length of the text string, and M is the length of the searchString. Additionally, there are some constant space variables like found and position.
Approach 3: Using std::search() Algorithm
Program:
Here's a code shown below demonstrates the usage of std::search() in C++:
#include <iostream>
#include <string>
#include <algorithm>
int main() {
// Define the input text and the string to search for
std::string text = "Hello, World!";
std::string searchString = "Java";
// Use std::search to find the occurrence of searchString in text
auto found = std::search(text.begin(), text.end(), searchString.begin(), searchString.end());
// Check if searchString was found
if (found != text.end()) {
// Calculate and print the position of the found substring
std::cout << "Found at position: " << found - text.begin() << std::endl;
} else {
// If not found, print a message
std::cout << "Not found in the text." << std::endl;
}
return 0;
}
Output:
Not found in the text.
Explanation:
- #include Directives:
In this example, the code begins with #include directives, which are used to include necessary header files. These directives include <iostream> for input and output, <string> for working with strings, and < Algorithm> for using the std::search algorithm.
- Variable Declarations:
std::string text = "Hello, World!";: Here, a string variable named text is declared and initialized with the value "Hello, World!". It is the text in which we will search.
std::string searchString = "Java";: Another string variable, searchString, is declared and initialized with the value "Java". It is the subsequence we want to find within the text string.
- Using std::search() Algorithm:
auto found = std::search(text.begin(), text.end(), searchString.begin(), searchString.end());: The std::search algorithm is used to find a subsequence (searchString) within a sequence (text). It takes two pairs of iterators: the range to search in (text.begin() to text.end()) and the range to search for (searchString.begin() to searchString.end()).
- Checking for the Subsequence:
if (found != text.end()) {: We check if the found iterator is not equal to text.end(). If it's not equal, it means that the subsequence was found within the text.
std::cout << "Found at position: " << found - text.begin() << std::endl;: If the subsequence was found, we calculate and print its position by subtracting text.begin() from found. It gives us the position within the entire text string.
If the found iterator is equal to text.end(), it means that the subsequence was not found in the text, so we print a message indicating that.
Complexity analysis:
Time Complexity:
The std::search() Algorithm has a time complexity of O(N*M), where N is the length of the text string, and M is the length of the searchString. It performs a linear search of the text, and in the worst case, it may need to check all possible subsequence positions.
Space Complexity:
The space complexity of this code is O(1) because it uses a constant amount of memory for variables like text, searchString, and found. The memory usage does not depend on the input sizes N and M.
Approach 4: Using a Manual Search Loop
Program:
Here's a code shown below demonstrates the usage of std::npos using a manual search loop in C++:
#include <iostream>
#include <string>
int main() {
std::string text = "Hello, World!";
std::string searchString = "Java";
for (size_t i = 0; i <= text.length() - searchString.length(); i++) {
// Iterate through potential positions
bool found = true; // Assume a match
for (size_t j = 0; j < searchString.length(); j++) {
// Compare characters
if (text[i + j] != searchString[j]) {
// If characters don't match
found = false; // Reset the flag
break; // Exit the inner loop
}
}
if (found) {
// If no mismatches occurred, a match was found
std::cout << "Found at position: " << i << std::endl; // Print the position
}
}
return 0;
}
Output:
Found at position:
Explanation:
- #include Directives:
In this example, the code starts with #include directives to include the necessary header files. These directives include <iostream> for input and output and <string> for working with strings.
- Variable Declarations:
std::string text = "Hello, World!";: This line declares and initializes a string variable named text with the value "Hello, World!". It is the text in which we want to search for the searchString.
std::string searchString = "Java";: Another string variable, searchString, is declared and initialized with the value "Java". It is the substring we are looking for in the text string.
- Manual Search Loop:
The code uses a nested loop structure to manually search for the searchString within the text string.
The outer loop, controlled by the variable i, iterates through potential starting positions within the text string. It runs from 0 to text.length() - searchString.length().
The inner loop, controlled by the variable j, compares characters between the searchString and the portion of text starting from the current position i. If characters do not match, the found flag is set to false. The inner loop is exited using the break statement.
- Checking for a Match:
After the inner loop completes, the code checks if the found flag is true. If no mismatches occur, it means that a match was found. In this case, the code prints the position where the match starts within the text string.
- Program Termination:
The code ends with return 0;, indicating a successful execution.
Complexity analysis:
Time Complexity:
The time complexity of this code is O(N*M), where N is the length of the text string, and M is the length of the searchString. In the worst case, the code may need to check all possible starting positions and compare all characters of searchString with the corresponding characters in the text string.
Space Complexity:
The space complexity is O(1) because the code uses a constant amount of memory for variables, and the memory usage does not depend on the input sizes N and M.