PROBLEM LINK: CodeChef: Practical coding for everyone
DIFFICULTY: Easy-Medium
PREREQUISITES: Implementation
EXPLANATION:
In this problem one needs to find the number of the substrings in the string S with a given prefix A and given suffix B. If we mark black all the starting positions of the entries of the string A in S, and white all the starting positions of the entries of the string B, then we come to the following problem: count the number of pairs <black position, white position> (in this order). To solve this it is enough to iterate from left to right counting the number of the passed black positions. Meeting black position we increment this number by one, meeting white position we add to the answer the number of pairs with this white position, which is exactly our memorized number of the already passed black positions.
SOLUTION:
(C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
string str;
cin>>str;
int i=0;
int coutn=0;
int ans=0;
while(i<str.size()-4){
if(str.substr(i,4)==“hail”){
coutn++;
i=i+4;
continue;
}
if(str.substr(i,5)==“hydra”){
ans=ans+coutn;
i=i+5;
continue;
}
i++;
}
cout<<ans;
return 0;
}