#include<iostream>
using namespace std;
int main ()
{
    int z=0;
    int count=0;
    int set=0;
    string str1="lol";
    string str2;
    cin>>str2;
    for(int x=0;x<str2.size();x  )
    {
        if(str1[z]==str2[x])
        {
            z  ;
            count  ;
            if(count==3)
                {
                    x--;
                    set  ;
                    z=0;
                    count=0;
                }
                else
                continue;
        }
         else
                continue;
        
    }
    cout<<set;

    return 0;
}

In this problem, you should print a number of "lol" in string S.

Input only string S (1<=|s|<=105).

Output print number of "lol" in string S.

Examples

input
lolol
output
2

input
llpol
output
0

input
lloll
output
1

i have problem in testcase 2 as it give me 1 but output should be zero what condition i should use to make this not happen but without using any built in function ?

CodePudding user response：

You need to use the so called "sliding window" approach.

This means, you iterate over the search string and then move a sliding window over it. The Window length is the size of the string to be found.

Example:

str2             abclololdef
window           | |
window content   abc           Now compare window with str1

slide 1 to the right:

str2             abclololdef
window            | |
window content    bcl       Now compare window with str1

slide 1 to the right:

str2             abclololdef
window             | |
window content     clo       Now compare window with str1

slide 1 to the right:

str2             abclololdef
window              | |
window content      lol       Now compare window with str1. Found. Increment counter

slide 1 to the right:

str2             abclololdef
window               | |
window content       olo       Now compare window with str1


slide 1 to the right:

str2             abclololdef
window                | |
window content        lol       Now compare window with str1. Found. Increment counter

slide 1 to the right:

str2             abclololdef
window                 | |
window content         old       Now compare window with str1. 

slide 1 to the right:

str2             abclololdef
window                  | |
window content          lde       Now compare window with str1. 

slide 1 to the right:

str2             abclololdef
window                   | |
window content           def       Now compare window with str1. 

Now, window is at end. Stop sliding.

You see. There is a window. The window has a start position and a width (the size of str1) and an end position which is "start position width"

Care must be taken, that we do not slide the window over the right boundary of str1.

For the comparision we compare position 0 of "lol" with str2[startIndex], then position 1 of "lol" with str2[startIndex 1] and position 2 of "lol" with str2[startIndex 2]. This we will do in a small loop.

This can be translated 1 to 1 to code:

#include <iostream>
#include <string>

int main() {
    // This is the string that we are looking for
    std::string stringToFind = "lol";

    // Get string to evaluate from user
    std::string stringToEvaluate{};
    std::cin >> stringToEvaluate;

    // The width of length of the window
    int width = stringToFind.length();

    // Hwer we sill store the number of times we find "lol"
    int counter = 0;

    // Now iterate over the comlete input string. Do NOT cross boundaries
    for (int k = 0; k < stringToEvaluate.length() - width;   k) {

        // Define the sliding window position
        int startPosition = k;
        int endPosition = k   width;
        int windowIndex = 0;

        //Here we will store, if we have a full OK comparison; Assum OK in the beginning
        bool allEqual = true;

        // Now compare the window ketter with the lol string
        for (int windowPositionIndex = startPosition; windowPositionIndex < endPosition;   windowPositionIndex) {
            
            // Compare window with base string
            if (stringToEvaluate[windowPositionIndex] != stringToFind[windowIndex]) {
                allEqual = false;
                break;

            }
            // Next letter of the search string
              windowIndex;
        }
        if (allEqual)   counter;
    }
    std::cout << counter << '\n';
}

I hope this is somehow understandable. If not then ask.

CodePudding user response：

Hope you dont mind this rewrite

#include <iostream>
#include <cstdint>
#include<iostream>

uint32_t count( const std::string& needle, const std::string& haystack ) 
{
    uint32_t count = 0;
    uint32_t n  = needle.size();    
    uint32_t size = haystack.size();
    for ( uint32_t j=0; j<size;   j ) {
        if ( haystack[j] == needle[0] ) {
            uint32_t left = size - j;
            if ( left >= n ) {
                bool found = true;
                for ( uint32_t k=0; k<n;   k ) {
                    if ( haystack[j k]!=needle[k] ) {
                        found = false;
                        break;
                    }
                }
                if ( found ) {
                    count  = 1;
                }
            }
        }
    }
    return count;
}

int main ( int argc, char* argv[] )
{
    std::string needle = "lol";
    std::cout << "Count:" << count( needle, argv[1] ) << std::endl;
    return 0;
}

Code: https://godbolt.org/z/hsPqfzrcM

Input:
llpol
Output:
0