| ||||||||||
| 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