Skip to content

Instantly share code, notes, and snippets.

@chenshuo
Created January 15, 2012 03:25
Show Gist options
  • Save chenshuo/1614144 to your computer and use it in GitHub Desktop.
Save chenshuo/1614144 to your computer and use it in GitHub Desktop.
poj1035
#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);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment