在位替换阵列的多个引用-yiteyi-C++库

给定一个字符串和一个模式，用字符“X”替换模式的多次出现。转换应该到位，解决方案应该替换 通过单个“X”多次连续（且不重叠）出现图案 .

null

String – GeeksForGeeksPattern – GeeksOutput: XforX String – GeeksGeeksPattern – GeeksOutput: XString – aaaaPattern – aaOutput: XString – aaaaaPattern – aaOutput: Xa

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

其想法是保留两个索引i和j，以便就地替换。索引i总是指向输出字符串中的下一个字符。索引j遍历字符串并搜索一个或多个模式匹配。如果找到匹配项，我们将字符“X”放在索引i处，并将索引i增加1，将索引j增加模式的长度。如果我们发现多个连续出现的模式，索引i只会增加一次。如果没有找到模式，我们将索引j处的当前字符复制到索引i，并将i和j都增加1。由于模式长度始终大于等于1，替换长度仅为1个字符，因此我们永远不会覆盖未处理的字符，即j>=i是不变的。

C++

                         // C++ program to in-place replace multiple                       
                         // occurrences of a pattern by character ‘X’                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // returns true if pattern is prefix of str                       
                         bool                                     compare(                                     char                                     * str,                                     char                                     * pattern)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; pattern[i]; i++)                       
                                                 if                                     (str[i] != pattern[i])                       
                                                 return                                     false                                     ;                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Function to in-place replace multiple                       
                         // occurrences of a pattern by character ‘X’                       
                         void                                     replacePattern(                                     char                                     * str,                                     char                                     * pattern)                       
                         {                       
                                                 // If pattern is null or empty string,                       
                                                 // nothing needs to be done                       
                                                 if                                     (pattern == NULL)                       
                                                 return                                     ;                       
           
                                                 int                                     len =                                     strlen                                     (pattern);                       
                                                 if                                     (len == 0)                       
                                                 return                                     ;                       
           
                                                 int                                     i = 0, j = 0;                       
                                                 int                                     count;                       
           
                                                 // for each character                       
                                                 while                                     (str[j]) {                       
                                                 count = 0;                       
           
                                                 // compare str[j..j+len] with pattern                       
                                                 while                                     (compare(str + j, pattern)) {                       
                                                 // increment j by length of pattern                       
                                                 j = j + len;                       
                                                 count++;                       
                                                 }                       
           
                                                 // If single or multiple occurrences of pattern                       
                                                 // is found, replace it by character 'X'                       
                                                 if                                     (count > 0)                       
                                                 str[i++] =                                     'X'                                     ;                       
           
                                                 // copy character at current position j                       
                                                 // to position i and increment i and j                       
                                                 if                                     (str[j])                       
                                                 str[i++] = str[j++];                       
                                                 }                       
           
                                                 // add a null character to terminate string                       
                                                 str[i] =                                     ' '                                     ;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 char                                     str[] =                                     "GeeksforGeeks"                                     ;                       
                                                 char                                     pattern[] =                                     "Geeks"                                     ;                       
           
                                                 replacePattern(str, pattern);                       
                                                 cout << str;                       
           
                                                 return                                     0;                       
                         }                       

输出：

XforX

上述算法的时间复杂度为O（n*m），其中n是字符串的长度，m是模式的长度。 STL的实现

The idea of this implementation is to use the STL in-built functions to search for pattern string in main string and then erasing it from the main string

C++

                         // C++ program to in-place replace multiple                       
                         // occurrences of a pattern by character ‘X’                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to in-place replace multiple                       
                         // occurrences of a pattern by character ‘X’                       
                         void                                     replacePattern(string str, string pattern)                       
                         {                       
           
                                                 // making an iterator for string str                       
                                                 string::iterator it = str.begin();                       
                                                 // run this loop until iterator reaches end of string                       
                                                 while                                     (it != str.end()) {                       
                                                 // searching the first index in string str where                       
                                                 // the first occurrence of string pattern occurs                       
                                                 it = search(str.begin(), str.end(), pattern.begin(), pattern.end());                       
                                                 // checking if iterator is not pointing to end of the                       
                                                 // string str                       
                                                 if                                     (it != str.end()) {                       
                                                 // erasing the full pattern string from that iterator                       
                                                 // position in string str                       
                                                 str.erase(it, it + pattern.size());                       
                                                 // inserting 'X' at that iterator position                       
                                                 str.insert(it,                                     'X'                                     );                       
                                                 }                       
                                                 }                       
           
                                                 // this loop removes consecutive 'X' in string s                       
                                                 // Example: GeeksGeeksforGeeks was changed to 'XXforX'                       
                                                 // running this loop will change it to 'XforX'                       
                                                 for                                     (                                     int                                     i = 0; i < str.size() - 1; i++) {                       
                                                 if                                     (str[i] ==                                     'X'                                     && str[i + 1] ==                                     'X'                                     ) {                       
                                                 // removing 'X' at position i in string str                       
                                                 str.erase(str.begin() + i);                       
                                                 i--;                                     // i-- because one character was deleted                       
                                                 // so repositioning i                       
                                                 }                       
                                                 }                       
                                                 cout << str;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 string str =                                     "GeeksforGeeks"                                     ;                       
                                                 string pattern =                                     "Geeks"                                     ;                       
           
                                                 replacePattern(str, pattern);                       
           
                                                 return                                     0;                       
                         }                       

输出：

XforX

本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章