Count overlapping occurrances of substring within string

Question

#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 ?

This doesn’t address the question, but those `else continue;` bits aren’t needed. — Pete Becker, Dec 23 '21 at 19:57
You always compare "lol" to the full string str2. So the answer is always wrong. You need to compare "lol" to a sub-string of str2. For this you should use the "substr" function with always the length of 3. Do not forget to add -3 in the for loops condition `x — A M, Dec 23 '21 at 19:59
this task without using any built in function @JohnnyMopp sorry i should tell that in my question — Golden_hacker_1, Dec 23 '21 at 20:00
Why not just use [str2.find(str1, pos)](https://en.cppreference.com/w/cpp/string/basic_string/find)? — Alan Birtles, Dec 23 '21 at 20:01
Does this answer your question? [Counting the number of occurrences of a string within a string](https://stackoverflow.com/questions/22489073/counting-the-number-of-occurrences-of-a-string-within-a-string) — anastaciu, Dec 23 '21 at 20:02
You can use an inner loop that basically simulates `strcmp`. Ex: https://onlinegdb.com/HTe2m8Uk0 — 001, Dec 23 '21 at 20:11
@Golden_hacker_1 *this task without using any built in function* -- If you were to use a "built-in function", which one would you use to solve the problem? Ok, now implement that function yourself, and call it instead of the "built-in function". Simple. — PaulMcKenzie, Dec 23 '21 at 20:28
You just need two nested loops. The outer loop advances one character at a time in `str2`. The inner loop compares with `str1`. — user3386109, Dec 23 '21 at 20:29

A M · Answer 1 · 2021-12-24T09:57:59.480

I answered rather early in the comments to your question (the 3rd comment) that you could use the approach with comparing "lol" with a substring of the big string to evaluate. Using the "substr" function.

Somebody else proposed the "find" function. Then you said in the 5th comment:

this task without using any built in function @JohnnyMopp sorry i should tell that in my question

So then, we should use the fully handcrafted so called "naive sliding window" approach. This is very simple to understand and for your use case completely sufficient.

I will first give a detailed explanation and then implement this idea in a simple approach with a simple programming style.

It will work without using any built in function, so it will be completely based on standard instructions.

How does this work?

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.

Normally, the window would simply be defined by a substr function, but, because you said that you do not want to have a function, we will use a 2nd loop. This will not slow down your program in any noticable way here.

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();

    // Here we will store the number of times we find "lol"
    int counter = 0;

    // Now iterate over the complete 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';
}

Because of the ultra simple programming style with creating many intermediate variables with "speaking" names and by writing many comments, this should be somehow understandable (I hope)

EDIT

I saw in comments that people were discussing about speed and big O notation. And that we could use KMP with an O(n+m) complexity.

I can show an even faster solution, with O(n-3), and I will still work without using any built in function during execution.

The idea is taken from Rabin-Karp. But, we can observe that we do not need to calculate hash values. We can directly convert a 3byte string to an 32bit unsigned integer. And then make comparisons on integer basis. Mening, we will treat the string as an overlapping integer array. So, we will first create a compile time constant hash value for the string "lol" (7106412) and then do the complete comparison with the string "lol" with one "cmp edx, 7106412" assembler instruction.

We take also advantage of the fact that std::string will be 0-terminated since C++11.

This will result in compact code (6 statements in main, inclusive output), outperforms everthing else in regards to speed and still works without using any built in function or library.

#include <iostream>
#include <string>

// Hash for the string that we are looking for
constexpr unsigned int hash = ('l' << 16) + ('o' << 8) + 'l';
// or: const unsigned int hash = *reinterpret_cast<const unsigned int*>("lol");

int main() {

    // Take any test string to evaluate
    std::string stringToEvaluate{ "aaaaalololbbbbbllpolcccccllollddddd" };

    // Here we will store the number of times we find "lol"
    unsigned int counter = 0;

    // Now iterate over the input string. Do not cross boundaries
    for (size_t k = 0; k < stringToEvaluate.length() - 3; ++k) {

        // Compare hash values
        if (hash == (*reinterpret_cast<unsigned int*>(&stringToEvaluate[k])) >> 8)
            ++counter;
    }
    std::cout << counter << '\n';
}

Compiled and tested with Microsoft Visual Studio Community 2019, Version 16.11.0 and gcc11.2 and Clang13 with "-O3 -Werror -Wall -Wpedantic"

The last code contains an *undefined behaviour* since `&stringToEvaluate[k]` is not aligned to `alignof(unsigned int)`. Moreover, `unsigned int` is not guaranteed to be 32-bit/4-bytes wide resulting in an *implementation-defined behaviour* (this one can be easily fixed using a `uint32_t`). — Jérôme Richard, Dec 30 '21 at 16:34
Thank you, Jerome for this very good analysis. According to the standard, you are absoluteley right. Of course, any compiler will translate it as expected. Otherwise, the compiler would be rejected. So, somehow an academical only comment (But of course true). And you may sleep well. In my world "reinterprete_cast" will not survive any static code analysis without justification by review of the created assemeler code for the assigned microntroller architecture. I think, the OP asking the question (although long gone) and others will be happy for this comment. So, you are correct. Thank you. — A M, Dec 30 '21 at 17:57

score 1 · Accepted Answer · 2021-12-23T22:07:17.063

The implementation count1 below will avoid creating a std::string if you pass a char pointer or a C string.

The second implementation count2 is probably yet more efficient.

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

std::size_t count1( const std::string_view& needle, const std::string_view& haystack ) 
{
    std::size_t count = 0;
    std::size_t n  = needle.size();    
    for ( std::size_t j=0; j<haystack.size()-n+1; ++j ) {
        if ( haystack.substr(j,n)==needle ) {
            count += 1;
        }
    }
    return count;
}

std::size_t count2( const std::string_view& needle, const std::string_view& haystack ) {
    std::size_t count =0;
    std:size_t pos = haystack.find( needle, 0 );
    while ( pos != std::string_view::npos ) {
        count += 1;
        pos = haystack.find( needle, pos+1 );
    } 
    return count;
}

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

Code: https://godbolt.org/z/9GG1TPcaM

Input:
llpol
Output:
0

This works, but has complexity O(N*M). The more optimal solution uses KMP algorithms in complexity O(N+M). Since one of the strings has length 3 it probably doesn't make a difference here. — Sorin, Dec 23 '21 at 22:01
@ArminMontigny Please don't do that. I am a strong believer of diversity of thoughts. We should have all in there to discuss. — , Dec 23 '21 at 22:05

Count overlapping occurrances of substring within string

2 Answers2