Ask Question

Name:
Title:
Your Question:

Answer Question

Name:
Your Answer:
User Submitted Source Code!


Description:
  aaa
Language: C/C++
Code:
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

// For a given string compute an array which, when a mismatch occurs, helps determine where the next match should begin, without re-examining previously matched characters
vector<int> computeSubstringSearchHelpArray(string str)
{
  vector<int> substringSearchHelpArray(str.size());
  int index = 0;
  int i;
  for (i = 1; i < str.size(); )
  {
    if (str[i] == str[index])
    {
      substringSearchHelpArray[i] = index + 1;
      index++;
      i++;
    }
    else
    {
      if (index != 0)
      {
        index = substringSearchHelpArray[index - 1];
      }
      else
      {
        substringSearchHelpArray[i] = 0;
        i++;
      }
    }
  }

  return substringSearchHelpArray;
}

// Knuth-Morris-Pratt string-searching algorithm which searches for occurrences of a string inside another string
// This has been adapted to work for the letter wheels considered in this problem
// Iterate through both strings and try to match characters;
// When a mismatch occurs, resume matching at another point, avoiding re-examination of previously matched characters
bool isMatch(vector<vector<bool> > wheels, string str)
{
  vector<int> substringSearchHelpArray = computeSubstringSearchHelpArray(str);
  int i = 0;
  int j = 0;
  while (i < wheels.size() && j < str.size())
  {
    if (wheels[i][tolower(str[j]) - 'a'])
    {
      i++;
      j++;
    }
    else
    {
      if (j != 0)
        j = substringSearchHelpArray[j - 1];
      else
        i++;
    }
  }

  if (j == str.size())
    return true;

  return false;
}

int main(int argc, char *argv[])
{
  // Check if the number of arguments provided is correct
  if (argc != 3)
  {
    // Report incorrect number of arguments and stop execution
    cout << "The program expects 2 arguments to be provided:" << endl;
    cout << "- the name of the file containing information about the wheels" << endl;
    cout << "- the name of a file contatining the list of words" << endl;
    cout << "Please provide the correct arguments." << endl;
    return 0;
  }

  // Wheels information
  int numberOfWheels;
  int numberOfLettersPerWheel;
  // 2-dimensional vector
  // where wheels[i][j] indicates if wheel i has letter j
  // where j represents letters a-z as numbers 0-25
  vector<vector<bool> > wheels;

  // Open the file containing the wheels information and check if the operation was successful
  ifstream wheelsInputFile;
  wheelsInputFile.open(argv[1]);
  if (wheelsInputFile.is_open())
  {
    // Read the number of wheels
    wheelsInputFile >> numberOfWheels;

    // Read the number of letters per wheel
    wheelsInputFile >> numberOfLettersPerWheel;

    // Read the wheels
    // Iterate until the required letters have been read
    int wheelNumber = 0, letterNumber = 0;
    for (wheelNumber = 0; wheelNumber < numberOfWheels; )
    {
      // Vector containing information about which letters a-z the wheel contains
      vector<bool> hasLetter(26);

      for (letterNumber = 0; letterNumber < numberOfLettersPerWheel; )
      {
        // Read a character and check if it is a letter
        char character = wheelsInputFile.get();
        if (tolower(character) - 'a' >= 0 && tolower(character) - 'a' <= 25)
        {
          // tolower(character) - 'a' return an integer in range [0, 25] representing a letter from a to z
          // characters are converted to lowercase
          hasLetter[tolower(character) - 'a'] = true;
          letterNumber++;
        }
      }

      wheels.push_back(hasLetter);
      wheelNumber++;
    }

    // Close the file
    wheelsInputFile.close();
  }
  else
  {
    // Report an error while opening the file
    cout << "There was an error while opening file: " << argv[1] << endl;
    return 0;
  }

  // Count the number of words found
  int numberOfWordsFound = 0;

  // Open the file containing the list of words and check if the operation was successful
  ifstream wordsInputFile;
  wordsInputFile.open(argv[2]);
  if (wordsInputFile.is_open())
  {
    // Read the words in the file one by one
    string word;
    while (wordsInputFile.good())
    {
      wordsInputFile >> word;

      // Check if the word can be formed with the given wheels
      if (isMatch(wheels, word))
      {
        cout << word << endl;
        numberOfWordsFound++;
      }
    }
  }
  else
  {
    // Report an error while opening the file
    cout << "There was an error while opening file: " << argv[2] << endl;
    return 0;
  }

  cout << numberOfWordsFound << endl;

  return 0;
}
Comments: