[ create a new paste ] login | about

Link: http://codepad.org/e80YEm17    [ raw code | fork ]

C++, pasted on Oct 13:
#include <bits/stdc++.h>
#include <cassert>
#include <climits>
#include <cfloat>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

/*
srand((unsigned)time(NULL));
inline unsigned int rand16(){return ((rand()) << 15) ^ rand();}
inline unsigned int rand32(){return (rand16() << 16) | rand16();}
inline ULL rand64(){return ((LL)rand32() << 32) | rand32();}
inline ULL random(LL l, LL r){return l == r ? l : rand64() % (r - l) + l;}
*/

const int INF = 0x3f3f3f3f;
const LL INFF = 1LL << 60;
const double EPS = 1e-9;
const double PI = acos(-1.0); //2*acos(0.0); //M_PI;

//4 dirs: int dx[]={1,0,-1,0}, dy[]={0,1,0,-1};
//8 dirs: int dx[]={1,1,0,-1,-1,-1,0,1}, dy[]={0,1,1,1,0,-1,-1,-1};
//hex: int dx[6]={2,1,-1,-2,-1,1}, dy[6]={0,1,1,0,-1,-1};
//knight: int dx[]={2,1,-1,-2,-2,-1,1,2}, dy[]={1,2,2,1,-1,-2,-2,-1};

#define FOR(i,a,b)   for(int(i)=int(a);(i)<int(b);(i)++)
#define FOREQ(i,a,b) for(int(i)=int(a);(i)<=int(b);(i)++)
#define RFOR(i,a,b)  for(int(i)=(a),_b(b);(i)>=_b;--(i))
#define FOREACH(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

#define FILL(arr,val) memset((arr),(val),sizeof(arr))
#define CLR(a)        memset((a),0,sizeof(a))
#define CPY(dest,src) memcpy((dest),(src),sizeof(dest))

#define ALL(a)       (a).begin(),(a).end()
#define SZ(a)        ((int)(a).size())
#define UNIQ(a)      sort(ALL(a)); (a).erase(unique(ALL(a)),(a).end())
#define IDX(arr,ind) (lower_bound(ALL(arr),ind)-arr.begin())

#define fst first
#define snd second
#define pb  push_back
#define mp  make_pair

template< typename T, size_t N >
inline void print_ary(T(&ary)[N], int er)
{
	for(int r = 0; r < er; r++)
	{
		cout << ary[r] << " ";
	}
	cout<<endl;
}
template< typename T, size_t N >
inline void print_ary_eq(T(&ary)[N], int er)
{
	for(int r = 1; r <= er; r++)
	{
		cout << ary[r] << " ";
	}
	cout<<endl;
}
template< typename T, size_t N, size_t M >
inline void print_ary_2d(T(&ary)[N][M], int er, int ec)
{
	for(int r = 0; r < er; r++)
	{
		for(int c = 0; c < ec; c++)
		{
			cout << ary[r][c] << " ";
		}
		cout<<endl;
	}
}
template< typename T, size_t N, size_t M >
inline void print_ary_2d_eq(T(&ary)[N][M], int er, int ec)
{
	for(int r = 1; r <= er; r++)
	{
		for(int c = 1; c <= ec; c++)
		{
			cout << ary[r][c] << " ";
		}
		cout<<endl;
	}
}
inline LL lcm(LL a, LL b)
{
	return a*b/__gcd(a,b);
}
inline double dist(double x1, double y1, double x2, double y2)
{
	return hypot(x1-x2,y1-y2);
}
//scanf("%[^\n]", &s);

#define MIN3(a, b, c) ((a) < (b) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c)))

static char s[100005], t[100005];
static int a,b,k, v0[100005], v1[100005];

inline int levenshtein()
{
	// if (a == 0 && b == 0) return 0;
	// if (a > 0 && b > 0 && k == 0) return -1;
	if (strcmp(s,t) == 0) return 0;
	int slen = strlen(s), tlen = strlen(t);

	// printf("read: s(s2-row)=%s; t(s1-col)=%s; a=%d; b=%d; k=%d\n", s,t,a,b,k);

	FOR(i,0,tlen)
	{
		v0[i] = i;
	}
	// printf("v0:    %02d  %02d ", v0[0],v0[1]);
	// FOR(i,2,tlen)
	// {
	// 	printf("%02d ", v0[i]);
	// }
	// printf("\n");

	FOR(i,0,slen)
	{
		if (i<=k)
		{
			v1[0] = i+1;
			FOR(j,0,min(i+k+1,tlen))
			{
				if (j == min(i+k,tlen-1))
				{
					v1[j+1] = min(
						v1[j] + a,
						v0[j] + (s[i]==t[j]?0: min(2*a,b) )
					);
				}
				else
				{
					v1[j+1] = min(min(
						v1[j] + a,
						v0[j+1] + a
					),
						v0[j] + (s[i]==t[j]?0: min(2*a,b) )
					);
				}
			}
		}
		else //i > k
		{
			v1[i-k] = k;
			FOR(j,i-k,min(i+k+1,tlen))
			{
				if (j == i-k)
				{
					v1[j+1] = min(
						v0[j+1] + a,
						v0[j] + (s[i]==t[j]?0: min(2*a,b) )
					);
				}
				else if (j == min(i+k,tlen-1))
				{
					v1[j+1] = min(
						v1[j] + a,
						v0[j] + (s[i]==t[j]?0: min(2*a,b) )
					);
				}
				else
				{
					v1[j+1] = min(min(
						v1[j] + a,
						v0[j+1] + a
					),
						v0[j] + (s[i]==t[j]?0: min(2*a,b) )
					);
				}
			}
		}

		// printf("i=%02d: [%02d] ", i,v1[0]);
		// FOR(j,1,tlen+1)
		// {
		// 	printf("%02d ", v1[j]);
		// }
		// printf("\n");

		if (i<=k)
		{
			FOR(j,0,min(i+k,tlen)+1)
			{
				v0[j] = v1[j];
			}
		}
		else //i > k
		{
			FOR(j,i-k-1,min(i+k+1,tlen)+1)
			{
				v0[j] = v1[j];
			}
		}
	}

	return v1[tlen];
}

inline void read(int &x)
{
	register int c = getchar_unlocked();
	x = 0;
	for(; (c<48 || c>57); c = getchar_unlocked())
		;
	for(; c>47 && c<58; c = getchar_unlocked())
	{
		x = (x<<1) + (x<<3) + c - 48;
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	FOR(i,0,T)
	{
		scanf("%s", s);
		scanf("%s", t);
//		read(a); read(b); read(k);
		scanf("%d%d%d", &a,&b,&k);
		int k_orig = k;
		k++;
		int ans = levenshtein();
		if (ans > k_orig) ans = -1;
		printf("%d\n", ans);
	}
	return 0;
}


Create a new paste based on this one


Comments: