PKU 1035 Spell checker

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;
    }
}