poj 1035

字符串的蛋疼问题，和两个字符串的相似度的算法不一样，只需要判断一个的就可以了，否则会超时的
  1 #include <iostream>
  2 #include <string>
  3 #include <vector>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <map>
  7 #include <algorithm>
  8 #include <list>
  9 #include <ctime>
 10 #include <set>
 11 #include <cstring>
 12 #include <queue>
 13 #include <cstdio>
 14 #include <stack>
 15 using namespace std;
 16 bool addone(const string& source, const string& target, int& ssz, int& tsz) {
 17     if (ssz != (tsz - 1)) {
 18         return false;
 19     } else {
 20         int tol = 0;
 21         int j = 0;
 22         for (int i = 0; i < tsz;) {
 23             if (source[i] == target[j]) {
 24                 i++;
 25                 j++;
 26             } else {
 27                 j++;
 28                 tol++;
 29                 if (tol > 1) {
 30                     return false;
 31                 }
 32             }
 33         }
 34         return true;
 35     }
 36 }
 37 bool delone(const string& source, const string& target, int& ssz, int& tsz) {
 38     return addone(target, source, tsz, ssz);
 39 }
 40 bool mutone(const string& source, const string& target, int& ssz, int& tsz) {
 41     if (ssz != tsz) {
 42         return false;
 43     } else {
 44         int tol = 0;
 45         for (int i = 0; i < ssz; i++) {
 46             if (source[i] != target[i]) {
 47                 tol++;
 48                 if (tol > 1) {
 49                     return false;
 50                 }
 51             }
 52         }
 53         return true;
 54     }
 55 }
 56 int EditDistance(const string& source, const string& target) {
 57     bool j1, j2, j3;
 58     int ssz = source.size();
 59     int tsz = target.size();
 60     int off=ssz>tsz?(ssz-tsz):(tsz-ssz);
 61     if(1<off)
 62         return false;
 63     j1 = addone(source, target, ssz, tsz);
 64     if (j1)
 65         return true;
 66     j2 = delone(source, target, ssz, tsz);
 67     if (j2)
 68         return true;
 69     j3 = mutone(source, target, ssz, tsz);
 70     if (j3)
 71         return true;
 72     return false;
 73 }
 74 int main() {
 75     int sz, dist, exist;
 76     string tmp;
 77     vector<string> dic;
 78     cin >> tmp;
 79     while (tmp != "#") {
 80         dic.push_back(tmp);
 81         cin >> tmp;
 82     }
 83     sz = dic.size();
 84     int sz2;
 85     cin >> tmp;
 86     vector<string> res;
 87     while (tmp != "#") {
 88         exist = 0;
 89         res.clear();
 90         for (int i = 0; i < sz; i++) {
 91             dist = EditDistance(dic[i], tmp);
 92             if (1 == dist) {
 93                 res.push_back(dic[i]);
 94             }
 95             if (dic[i] == tmp) {
 96                 exist = 1;
 97                 break;
 98             }
 99         }
100         if (1 == exist) {
101             cout << tmp << " is correct\n";
102         } else {
103             sz2 = res.size();
104             cout << tmp << ":";
105             for (int a = 0; a < sz2; a++) {
106                 cout << " " << res[a];
107             }
108             cout << endl;
109         }
110         cin >> tmp;
111     }
112     return 0;
113 }
from kakamilan