Finding a Pair of character in a string

Question

#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        int count = 0;
        vector<string> v;
        string resp;
        cin >> resp;
        v.push_back(resp);
        for(int i = 0; i < v.size(); i++){
            if(find(v.begin(), v.end(), "xy") != v.end()){
                count++;
        }
        cout << count << endl;
   }
   return 0;
}

I want to find the character "xy" in the string for multiple test cases. For input xy, my count value outputs correctly as 1.

But for the input xyxxy instead of 2 it gives the value as 0 It is only finding the value once but i want to check the count of xy in whole string

I tried to use the substring function as well but it failed to work

**Recommended reading:** [Why should I not #include ?](https://stackoverflow.com/q/31816095/560648) — Asteroids With Wings, Jun 07 '20 at 18:09

einpoklum · Answer 1 · 2020-06-07T19:50:59.527

0

You're looking for "xy" within a vector of strings, which in your example, has a single element, "xyxxy". Since "xy" is not equal to "xyxxy", you're not finding any matches.

But even if you tried to std::find "xy" within "xyxxy" itself - that would fail too, since std::find looks for a single element within a range (or rather, iterator pair).

Instead, you can use the string::find() method, as described here; or, as the case may be, std::string_view::find():

#include <string>
#include <vector>
#include <iostream>
#include <string_view>

int main() {
    const std::string needle{"xy"};
    std::string haystack;
    std::cin >> haystack;
    std::size_t count{0};
    std::string_view remainder{haystack};
    while(true) {
        auto first_pos = remainder.find(needle);
        if (first_pos == std::string_view::npos) { break; }
        count++;
        remainder = remainder.substr(first_pos+needle.length());
    }
    std::cout << "Found " << count << " occurrences of \"" << needle << "\"\n";
}

Note: This does not account for overlapping occurrences. If you want those, you could either always increase the starting position by just 1; or make your solution more complex by employing something Boyer-Moore or Knuth-Morris-Pratt search (see String search algorithms), and resuming it at the correct state after each occurrence found.

edited Jun 07 '20 at 19:50

answered Jun 07 '20 at 17:34

einpoklum

118,144
57
340
684

it uses more memory space. Do you have any solution which takes minimum space complexity ? – RAGHAVENDRA DUBEY Jun 08 '20 at 07:53
@RAGHAVENDRADUBEY: This uses `O(1)` extra space; I'm not sure what you mean. Perhaps you're confusing `std::string_view` and `std::string`? – einpoklum Jun 08 '20 at 09:04
@RAGHAVENDRADUBEY: Send you my what? At any rate, the answer is probably no. – einpoklum Jun 08 '20 at 10:21
Can you help me in my recent question ? – RAGHAVENDRA DUBEY Jun 08 '20 at 10:39
I am getting a TLE error using this solution. S can contain only letters X and Y. And S is a size of N. And N's size is between 1-10^5. the sum of N over all test cases does not exceed 3⋅ – RAGHAVENDRA DUBEY Jun 08 '20 at 10:48
@RAGHAVENDRADUBEY: I don't know what you're compiling and running and with what inputs. But - maybe it's just the fact that the program takes different inputs than the the program in your question. – einpoklum Jun 08 '20 at 12:54

score 0 · Answer 2 · answered Jun 07 '20 at 17:35

I don't get the idea of while loop but that worked for me.

#include <iostream>
#include <vector>

int main()
{
    std::string str;
    std::cin >> str;
    int count = 0;
    for (int i(0); i < str.size()-1; ++i)
    {
        if ((str[i] == 'x') && (str[i + 1] == 'y'))
        {
            ++count;
        }
    }
    std::cout << count;
}

Finding a Pair of character in a string

2 Answers2