poj1035

poj1035.cc

#include <string>
#include <set>
#include <vector>
#include <iostream>
#include <assert.h>
#include <stdio.h>

using namespace std;
typedef vector<string> Dictionary;

bool diffByOne(const string& replace, const string& word)
{
  assert(word.size() == replace.size());
  string::const_iterator result = mismatch(word.begin(), word.end(), replace.begin()).first;
  if (result != word.end())
  {
    int pos = result - word.begin() + 1;
    return equal(word.begin()+pos, word.end(), replace.begin()+pos);
  }
  return false;
}

bool deleteOne(const string& source, const string& target)
{
  assert(source.size() == target.size()+1);

  string::const_iterator result = mismatch(target.begin(), target.end(), source.begin()).first;
  if (result != target.end())
  {
    int pos = result - target.begin();
    return equal(result, target.end(), source.begin()+pos+1);
  }
  return true;
}

bool match(const string& replace, const string& word)
{
  if (word.size() == replace.size() + 1)
  {
    return deleteOne(word, replace);
  }
  else if (word.size() == replace.size())
  {
    return diffByOne(replace, word);
  }
  else if (word.size() + 1 == replace.size())
  {
    return deleteOne(replace, word);
  }
  return false;
}

void check(const Dictionary& dict, const string& word)
{
  printf("%s:", word.c_str());
  for (Dictionary::const_iterator it = dict.begin();
      it != dict.end();
      ++it)
  {
    if (match(*it, word))
    {
      printf(" %s", it->c_str());
    }
  }
  printf("\n");
}

int main()
{
  string line;
  Dictionary dict;
  set<string> words;
  bool inTest = false;
  cin.sync_with_stdio(false);
  while (getline(cin, line))
  {
    if (line == "#")
    {
      if (inTest)
      {
        break;
      }
      else
      {
        inTest = true;
        continue;
      }
    }

    if (inTest)
    {
      if (words.find(line) != words.end())
      {
        printf("%s is correct\n", line.c_str());
      }
      else
      {
        check(dict, line);
      }
    }
    else
    {
      dict.push_back(line);
      words.insert(line);
    }
  }
}