Need help with C++ assignment!

[kim12]

Can someone please help me? I can't figure out how to code this assignment I have. The assignment is that I have to look for overlaps.

Example of Overlap:

Keyword: face

Comparison words: fact war stare cent facet endface

# Overlap between face and fact: 0
# Overlap between face and war: 0
# Overlap between face and stare: 0
# Overlap between face and cent: 2 (ce)
# Overlap between face and facet: 4 (face)
# Overlap between face and endface: 4 (e and face, but we take the bigger overlap)

Do you get it? So an overlap happens if the end of the keyword overlaps with the beginning of the comparison word, or the beginning of the keyword with the end of the comparison word.

Also, I need to take into account the max overlap. So in this example, my keyword was face and my biggest overlap was 4 (but since there were two 4's, I take the input that occurred first).

Thus, if I output the results to the screen after going through every input, I should get:

Keyword: face
Match: facet
Overlap: 4

Here's what I have so far...

#include <iostream>

using namespace std;

int overlapFront(string& , string& );

int overlapEnd(string& , string& );

void overlapMax(int& , string& , int , string&);

int main()  
{
    string input;
    int overlap = 0;
    int overlap2 = 0;
    int newMax = 0;
    
    int oldMax = 0;
    string oldInput = " ";
    
    string key1, key2, key3;
    
    cin >> key1; // testing only one keyword right now
    
    while (cin >> input)
    {
        overlap = overlapFront(key1, input);
        
        overlap2 = overlapEnd(key1, input);
        
        if (overlap2 > overlap)
        {
            newMax = overlap2;
        }
        
        else if (overlap == 0 && overlap2 == 0)
        {
            newMax = 0;
        }
        
        else if (overlap > overlap2)
        {
            newMax = overlap;
        }
        
        overlapMax(oldMax, oldInput, newMax, input);

        
        cout << "Key: " << key1 << endl;
        cout << "Match: " << input << endl;
        cout << "Overlap: " << overlap << " " << overlap2 << endl;
        
        cout << "Max: " << newMax << endl << endl;
        
    }
    
    return 0;
}

int overlapFront(string& key1, string& input)
{
    int overlap = 0;
    string match1 = input;
    string key = key1;
    
    if (input.substr(0, key1.size()) == key1)
    {
        overlap = key1.size();
        match1 = input;
    }
    
    return overlap;
}

int overlapEnd(string& key1, string& input)
{
    int overlap = 0;
    string match = input;
    string key = key1;
    
    if (input.at(input.size() - 1) == key1.at(0))
    {
        overlap = 1;
        match = input;
    }
    
    return overlap;
}

void overlapMax(int& oldMax, string& oldInput, int newMax, const string& cnst)
{
    int maxInt = oldMax;
    string maxS = oldInput;
    string newS = cnst;
    
    if (newMax > maxInt)
    {
        oldMax = newMax;
        oldInput = newS;
    }
}

I have used 3 functions. One for getting the # of overlaps at the front, one at the back, and for the max overlap and its associated string (input). But I am not complete as I don't know how to test for cases like face and cent (overlap = 2), or cases like face and sofa (overlap = 2), etc.

Also, I'm doing my overlapMax function wrong because when I compile, there was a problem with it. Please help if you can.. I really need to get this done today. Thank you!!

[kim12]

Anyone?

[cire]

This not the most efficient way to do this, but it should get the idea across:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::size_t overlap(const std::string& key, const std::string& word);
std::size_t forwardOverlap(const std::string&, const std::string&);
std::size_t reverseOverlap(const std::string&, const std::string&);

struct wordInfo
{
    std::size_t expectedOverlap;
    std::string word;
};

void testOverlap(const std::string& key, const std::vector<wordInfo>& words)
{
    for (auto& word : words)
    {
        std::size_t overlapSize = overlap(key, word.word);
        if (overlapSize != word.expectedOverlap)
        {
            std::cout << "overlap failed on key \"" << key;
            std::cout << "\" with word \"" << word.word << "\"\n";
            return;
        }
        //else
        //{
        //    std::cout << "overlap succeeded on key \"" << key;
        //    std::cout << "\" with word \"" << word.word << "\": ";
        //    std::cout << overlapSize << " overlap.\n";
        //}
    }

    std::cout << "overlap test successful!\n";
}


int main()
{
    std::vector<wordInfo> words =
    {
        { 0, "fact" }, 
        { 0, "war" }, 
        { 0, "stare" }, 
        { 2, "cent" }, 
        { 4, "facet" }, 
        { 4, "endface" },
        { 2, "alfalfa" }
    };

    testOverlap("face", words);
}

std::size_t overlap(const std::string& key, const std::string& word)
{
    return std::max(forwardOverlap(key, word), reverseOverlap(key, word));
}

std::size_t forwardOverlap(const std::string& k, const std::string& w)
{
    std::size_t overlapSize = std::min(k.size(), w.size());

    while (overlapSize > 0)
    {
        std::string keyFragment = k.substr(k.size() - overlapSize);
        std::string wordFragment = w.substr(0, overlapSize);

        if (keyFragment == wordFragment)
            break;

        --overlapSize;
    }

    return overlapSize;
}

std::size_t reverseOverlap(const std::string& k, const std::string& w)
{
    std::size_t overlapSize = std::min(k.size(), w.size()) ;

    while (overlapSize > 0)
    {
        std::string keyFragment = k.substr(0, overlapSize);
        std::string wordFragment = w.substr(w.size() - overlapSize);

        if (keyFragment == wordFragment)
            break;

        --overlapSize;
    }

    return overlapSize;
}

http://ideone.com/r7KHpP

[kim12]

Actually... it kind of did, but I couldn't follow as well since I'm a beginner programmer.

I figured out how to do my coding better and I ALMOST have it.

The only problem left is figuring out how to do the reverse overlap and forward overlap.

How would I go about coding something that overlaps like for example, face and cent, or face and sofa using if/else statements?

Following this structure:

int overlapBeg(string& key1, string& input)
{
    int overlap = 0;
    string match1;
    
    if (input.substr(0, key1.size()) == key1) // covers face and facet
    {
        overlap = key1.size();
        match1 = input;
    }
    
    else if (input.at(0) == key1.at(key1.size() - 1)) // covers face and end
    {
        overlap = 1;
    }

/* need code here covering face and acer */
    
    return overlap;
}

int overlapEnd(string& key1, string& input)
{
    int overlap = 0;
    string match = input;
    string key = key1;
    
    if (input.at(input.size() - 1) == key1.at(0)) // covers face and staff
    {
        overlap = 1;
        match = input;
    }

/* need code here covering face and sofa */
    
    return overlap;
}

It doesn't have to be strictly compared to these words. It needs to work for all words that overlap. It could be any word, like face and effac, etc.

I was thinking of using for loops to test each letter and using substr but I'm not sure how that would work. How can I work this out?

[cire]

How would I go about coding something that overlaps like for example, face and cent, or face and sofa using if/else statements?

It cannot be done with just if/else statements. You require a loop or recursion. See the code I supplied previously for an iterative example.