Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstring>
- #include <cstdio>
- #include <climits>
- using namespace std;
- int const MAX = 2000010;
- int const mx = 51;
- char s1[MAX], s2[mx];
- int d1[mx], d2[mx], l1[mx], l2[mx];
- int main()
- {
- int dp, n;
- gets(s1); gets(s2);
- scanf("%d", &dp);
- n = strlen(s2);
- for( int j=0; j<=n; j++ ) {
- d1[j] = j;
- d2[j] = INT_MAX;
- l1[j] = n - j;
- }
- int jj = strlen(s1);
- for( int i=1; i<=jj; i++ )
- {
- d2[0] = 0;
- l2[0] = n;
- for( int j=1; j<=n; j++ ){
- if( d2[j] > d2[j-1] + 1 ){
- d2[j] = d2[j-1] + 1;
- l2[j] = l2[j-1] - 1;
- }
- if (d2[j] > d1[j] + 1) {
- d2[j] = d1[j] + 1;
- l2[j] = l1[j] - 1;
- }
- if (d2[j] > d1[j-1] + (s1[i-1] != s2[j-1])) {
- d2[j] = d1[j-1] + (s1[i-1] != s2[j-1]);
- l2[j] = l1[j-1];
- }
- }
- /*
- printf("\n - %d\n", i);
- for (int i=1; i<=n; i++) {
- printf("%d ", d2[i]);
- }
- printf("\n");*/
- if( d2[n] <= dp )
- {
- printf("%d %d\n", i-l2[n], l2[n]);
- return 0;
- }
- memcpy( d1, d2, sizeof(d2) );
- memcpy( l1, l2, sizeof(l2) );
- for( int j=0; j<=n; j++ ) d2[j] = INT_MAX;
- memset(l2, 0, n);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement