Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
一次AC,纪念一下^-^/****************************************************/ /* File : POJ136.c */ /* Author : Zhang Yufei */ /* Date : 2015-12-13 */ /* Description : POJ ACM program. (submit:g++) */ /****************************************************/ #include<stdio.h> #include<string.h> // The s and t string in the problem. char s[100003]; char t[100003]; // The matrix used to calculate MSL. // The row is too large, so use only 2 lines repeatly. short matrix[2][100003]; /* * Used to deal with one input case. */ void butler(void); /* * Initial the matrix before deal with one case. */ void init(void); /* * The main program. */ int main(void) { while(scanf("%s %s", s, t) != EOF) { init(); butler(); } return 0; } /* * Used to deal with one input case. */ void butler(void) { int sl = strlen(s); int tl = strlen(t); for(int i = 1; i <= sl; i++) { int r = i % 2; for(int j = 1; j <= tl; j++) { if(s[i - 1] == t[j - 1]) { matrix[r][j] = matrix[1 - r][j - 1] + 1; } else { if(matrix[1 - r][j] > matrix[r][j - 1]) { matrix[r][j] = matrix[1 - r][j]; } else { matrix[r][j] = matrix[r][j - 1]; } } } } if(matrix[sl % 2][tl] == sl) { printf("Yes\n"); } else { printf("No\n"); } } /* * Initial the matrix before deal with one case. */ void init(void) { for(int i = 0; i < 2; i++) { for(int j = 0; j < 100003; j++) { matrix[i][j] = 0; } } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator