PKU 1035 Spell checker
手抜きで編集距離=1としたらTLEだった。
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; bool replace( string a, string b ); int main() { vector<string> dict; while ( true ) { string s; cin >> s; if ( s == "#" ) break; dict.push_back( s ); } while ( true ) { string s; cin >> s; if ( s == "#" ) break; cout << s; bool f = false; for ( int i=0; i<(int)dict.size() && !f; i++ ) if ( s == dict[i] ) cout << " is correct" << endl, f = true; if ( ! f ) { cout << ":"; for ( int i=0; i<(int)dict.size(); i++ ) if ( replace( dict[i], s ) ) cout << " " << dict[i]; cout << endl; } } } bool replace( string a, string b ) { int n = (int)a.length(); int m = (int)b.length(); int p = 0; while ( p<n && p<m && a[p]==b[p] ) p++; if ( p == n && p == m ) return false; if ( n < m ) { string t = a.substr(0,p) + b[p] + a.substr(p); return t == b; } else if ( n > m ) { string t = b.substr(0,p) + a[p] + b.substr(p); return a == t; } else { b[p] = a[p]; return a == b; } }