Hello! In this article, we will explore the problem of finding strings using C++. Solving algorithmic problems helps improve programming skills and assists in achieving good results in coding tests. Particularly in recent years, string manipulation problems have frequently appeared in coding tests. Therefore, a thorough understanding and practice of this topic are necessary.<\/p>\n
In this lecture, we will address the problem of finding a specific string (pattern) within a given text and counting how many times that string appears in the text. This problem serves as a fundamental example of string search algorithms and will solve the following problem.<\/p>\n
Problem:<\/strong> <\/p>\n Given a string There are several algorithms that can be used to solve the problem, but we will look at a simple brute force method here. This method checks each position in the text against the pattern to determine if they match. The performance is O(n * m), where n is the length of the text and m is the length of the pattern. This method is straightforward and intuitive, but one might also consider more efficient methods like the KMP algorithm or the Rabin-Karp algorithm.<\/p>\n Let’s implement the code. Below is a string-finding program written in C++:<\/p>\n The above C++ code solves the string-finding problem. It performs functions based on the The brute-force approach described above has a worst-case time complexity of O(n * m). As the length of the text increases, performance may degrade. However, if simplicity and intuitiveness are prioritized, this method can be useful.<\/p>\n For an efficient solution, consider the KMP (Knuth-Morris-Pratt) algorithm. The KMP algorithm optimizes string searches by utilizing repeated parts of the pattern. This algorithm has a time complexity of O(n + m).<\/p>\n The KMP algorithm is designed to solve pattern search problems and reduces repetitive checks by utilizing previously matched parts. This algorithm consists of two main steps. The first step builds an ‘LPS (Longest Prefix Suffix)’ array for the pattern, and the second step uses this LPS array to search for the pattern in the text.<\/p>\n The LPS array stores the lengths of the longest prefixes and suffixes among each prefix of the pattern. For example, for the pattern “ABAB,” the LPS array becomes [0, 0, 1, 2]. This has the following implications:<\/p>\n Below is the C++ code that implements the KMP algorithm:<\/p>\n In this article, we learned how to solve the string-finding problem using C++. After introducing the brute-force method, we explored how the efficient KMP algorithm operates. Problems related to strings can further develop based on basic algorithm knowledge. Therefore, it is essential to continue practicing such problems to enhance programming skills.<\/p>\n Try solving various string problems and develop your own algorithms! You’ll gain confidence in coding tests. Thank you!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"text<\/code> and pattern<\/code>, write a program to determine how many times pattern<\/code> appears in text<\/code>.<\/p>\nInput Format<\/h3>\n
\n
text<\/code> (1 \u2264 |text| \u2264 100,000)<\/li>\npattern<\/code> (1 \u2264 |pattern| \u2264 100,000)<\/li>\n<\/ul>\nOutput Format<\/h3>\n
\n
Approach<\/h2>\n
Code Implementation<\/h2>\n
\n#include <iostream>\n#include <string>\n\nint countOccurrences(const std::string &text, const std::string &pattern) {\n int count = 0;\n int textLength = text.length();\n int patternLength = pattern.length();\n\n for (int i = 0; i <= textLength - patternLength; i++) {\n \/\/ Compare substring through partial string comparison\n if (text.substr(i, patternLength) == pattern) {\n count++;\n }\n }\n return count;\n}\n\nint main() {\n std::string text, pattern;\n\n std::cout << \"Enter text: \";\n std::getline(std::cin, text);\n std::cout << \"Enter pattern: \";\n std::getline(std::cin, pattern);\n\n int occurrences = countOccurrences(text, pattern);\n std::cout << \"The pattern appears \" << occurrences << \" times.\" << std::endl;\n\n return 0;\n}\n<\/code><\/pre>\nCode Explanation<\/h2>\n
text<\/code> and pattern<\/code> provided by the user.<\/p>\n\n
pattern<\/code> in the given text<\/code>. It extracts substrings from each position in the text and increases the count whenever there is a match with the given pattern.<\/li>\ncountOccurrences<\/code> function to print the result.<\/li>\n<\/ul>\nPerformance Analysis<\/h2>\n
KMP Algorithm Introduction<\/h2>\n
Building the LPS Array<\/h3>\n
\n
KMP Algorithm Implementation<\/h3>\n
\n#include <iostream>\n#include <string>\n#include <vector>\n\nstd::vectorConclusion<\/h2>\n