Lev K
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <math.h> #include <limits.h> using namespace std; // Datatypes typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; // Define #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++) #define MP make_pair // Constants const double eps = 1e-8; const double PI = 3.1415926535897932384626433832795; #define INPUT_FILE "distance.in" #define OUTPUT_FILE "distance.out" string s1; string s2; vi r; // Time O(K*L) // Memory O(K) int main(void) { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else freopen(INPUT_FILE, "r", stdin); freopen(OUTPUT_FILE, "w", stdout); #endif s1.resize(100010); s2.resize(100010); getline(cin, s1); getline(cin, s2); int kk; cin >> kk; if(s2.size() > s1.size()) swap(s1, s2); int N = s1.size(), K = s2.size(); int mod = 2*kk+1; r.resize(mod); for(int i = 0; i < mod; i++) r[i] = i; int j = 1; for(int i = 1; i <= N; i++) { int l = max(j-kk, 1); int h = min(j+kk, K); if(l == 1) r[0] = i; int p = i - 1; for(int jj = l; jj <= h; jj++) { int t = r[jj%mod]; r[jj%mod] = min(min(t + 1, r[(jj-1)%mod] + 1), p + ((s1[i-1] == s2[jj-1])?0:1)); p = t; } j++; } if(r[K%mod] > kk) cout << "Infinity" << endl; else cout << r[K%mod] << endl; return 0; }
page revision: 0, last edited: 15 Oct 2008 11:13