String inside string

[Oriol Serrabassa]

Write a program that reads a sequence of words and prints, for each word, all the other words of the sequence contained in it.

Your program has to implement and use the function bool conte (string s1, string s2)

that returns true, if the word |s1| contains the word |s2| under the precondition that the length of |s1| is greater or equal than the length of |s2|.

Input format
Input consists in a natural number n followed by n different words p1,…,pn.

Output format
The program has to print a line for each p1,…,pn in this order. Each line starts with pi, followed by the symbol “:” and the list of all the input words contained in pi, in the same order than the input. Notice that the list corresponding to each pi always includes pi, since every word contains itself.


As usual my program works fine with the public inputs, however the privates give a wrong answer.

Public test case
INPUT 1
9
lighten
in
o
en
building
light
build
enlightenment
world

OUTPUT 1
lighten: lighten en light
in: in
o: o
en: en
building: in building build
light: light
build: build
enlightenment: lighten en light enlightenment
world: o world

INPUT 2
9
rem
pa
o
re
paraula
em
para
remor
mor

OUTPUT 2
rem: rem re em
pa: pa
o: o
re: re
paraula: pa paraula para
em: em
para: pa para
remor: rem o re em remor mor
mor: o mor


Lastly, the code. I will make a brief explanation of what this does after the code itself.

#include <iostream>
#include <vector>
using namespace std;

bool conte (string s1, string s2) {
	int counter = 0, i_reducer = 0;
	bool increase = true;
	for (int i = 0; i < s2.size(); ++i) {
		for (int j = 0; j < s1.size(); ++j) {
			if (s2[i] == s1[j]) {
				++counter, ++i, ++i_reducer, increase = true;
				if (counter == s2.size()) {
					cout << " ";
					return true;
				}
			}
			else {
				counter = 0;
				if (increase) {
					increase = false;
					i -= i_reducer;
				}
			}
		}
	}
	return false;
}

int main () {
	int size;
	cin >> size;
	vector <string> s (size);
	for (int i = 0; i < size; ++i) cin >> s[i];
	for (int i = 0; i < size; ++i) {
		cout << s[i] << ":";
		for (int j = 0; j < size; ++j) {
			if (s[i].size() >= s[j].size() and conte (s[i], s[j])) {
				cout << s[j];
			}
		}
		cout << endl;
	}
}

Main function
Variables declaration
Write vector
2 loops for checking all the other strings with each string
Condition to call conte function: s[i].size() >= s[j].size()

The condition is this one because there is no need to check if a bigger string is inside a smaller one since it is impossible.

Conte function
Variable declaration

I use counter to see how many consecutive chars both strings share. When chars aren't equal I reset counter to 0

i_reducer and increase go together. They are used when the smaller string share some characters with the bigger one but it isn't inside of it. An example would be "India" "Inda"

2 loops with each one being limited by the size of the strings

[Oriol Serrabassa]

Found a type of input (and similars) where program gave wrong answer:

2
gtl
ggtl

Fixed this by changing this:

if (increase) {
	increase = false;
	i -= i_reducer;
}

for this:

if (increase) {
	increase = false;
	i -= i_reducer;
	j -= i_reducer;
}

Now with those types of input, my program should be fixed but private inputs still give wrong outputs

[Oriol Serrabassa]

Tomorrow, I will test this new function which I believe it's an improved version and hopefully program gets accepted.

bool conte (string s1, string s2) {
	int counter = 0, i = 0, j = 0, i_save = 0, j_save = 0;
	bool save = true, load = false;
	while (i < s1.size() and j < s2.size()) {
		if (s2[j] == s1[i]) {
			if (save) i_save = i, j_save = j, save = false, load = true;
			++counter, ++i, ++j;
			if (counter == s2.size()) {
				cout << " ";
				return true;
			}
		}
		else {
			if (load) counter = 0, i = i_save + 1, j = j_save, save = true, load = false;
			else counter = 0, ++i;
		}
	}
	return false;
}

[JLBorges]

bool conte( std::string s1, std::string s2 )
{
    // search for string s2 in s1
    // http://www.cplusplus.com/reference/string/string/find/
    const auto pos = s1.find(s2) ;

    // If s2 was not found, the function returns string::npos.
    return pos != std::string::npos ; // return true if s2 was found within s1
}

[gunnerfunner]

how about using std::regex:

//#include <regex>
bool conte (const std::string& lhs, const std::string& rhs)
{
    if (lhs.size() < rhs.size())return false;
    std::regex input{rhs};
    std::smatch m{};
    std::regex_search(lhs, m, input);

    return (m.size() ? true : false);
}

edit: just seen the above post and I'd go with the std::string::find() option as it would be undoubtedly quicker than std::regex

[Oriol Serrabassa]

Okay, thanks for all the contributions however my program finally got accepted with my code.

#include <iostream>
#include <vector>
using namespace std;

bool conte (string s1, string s2) {
	int counter = 0, i = 0, j = 0, i_save = 0, j_save = 0;
	bool save = true, load = false;
	while (i < s1.size() and j < s2.size()) {
		if (s2[j] == s1[i]) {
			if (save) i_save = i, j_save = j, save = false, load = true;
			++counter, ++i, ++j;
			if (counter == s2.size()) {
				cout << " ";
				return true;
			}
		}
		else {
			if (load) counter = 0, i = i_save + 1, j = j_save, save = true, load = false;
			else counter = 0, ++i;
		}
	}
	return false;
}

int main () {
	int size;
	cin >> size;
	vector <string> s (size);
	for (int i = 0; i < size; ++i) cin >> s[i];
	for (int i = 0; i < size; ++i) {
		cout << s[i] << ":";
		for (int j = 0; j < size; ++j) {
			if (s[i].size() >= s[j].size() and conte (s[i], s[j])) {
				cout << s[j];
			}
		}
		cout << endl;
	}
}

Anyway I also tested both functions you created:
@JLBorges one got accepted.
@gunnerfunner one uses regex which is part of C++11 so I should avoid it. He also even suggests to use JLBorges' function.

Hurts a bit to see how my function got converted from 19 lines of code to 8 but I got to learn something really useful so I guess I cannot complain.

The best function for this program that has been accepted is this one (had to adapt JLBorge's const auto to const int and make changes to match output format):

bool conte (string s1, string s2) {
    const int pos = s1.find(s2);
    if (pos != string::npos) {
        cout << " ";
        return true;
    }
    else return false;
}

[JLBorges]

> Hurts a bit to see how my function got converted from 19 lines of code to 8

Could be (assumes that std::cout << ' ' will never fail).

bool conte( std::string s1, std::string s2 )
{
    return ( s1.find(s2) != std::string::npos ) && ( std::cout << ' ' ) ;
}

[Oriol Serrabassa]

Is it legit to use cout as a condition in an if, logic door, etc? Will it always be interpreted as true?

(xxxx) && (std::cout << ' ' ) 

[mbozzi]

Is it legit to use cout as a condition in an if statement?

Since std::cout is a std::basic_ostream<>, it's contextually convertible to bool. It evaluates to true if the stream is not in a failure state.
http://en.cppreference.com/w/cpp/io/basic_ios/operator_bool

Remember that std::basic_ostream<>::operator<< returns a reference to itself -- that's why you can chain sequences of print operations with <<.

[Oriol Serrabassa]

Is there any benefit in using cout as a condition rather than saving code lines?

[mbozzi]

Not that I can think of. You can always test it on the next line.

[JLBorges]

> Is there any benefit in using cout as a condition rather than saving code lines?

Using an input stream as a loop condition is idiomatic.

This operator makes it possible to use streams and functions that return references to streams as loop conditions, resulting in the idiomatic C++ input loops such as

while(stream >> value) {...} or while(getline(stream, string)){...}.

Such loops execute the loop's body only if the input operation succeeded. http://en.cppreference.com/w/cpp/io/basic_ios/operator_bool

Sometimes, in an interactive program, it is convenient to add the prompt as part of the condition.
while( std::cout << "enter a number: " && std::cin >> number ) { /* ... */ }