WOJ 1047 LCS problem （LCS 算法总结 ）
时间：2022-03-23 23:17
http://acm.whu.edu.cn/land/problem/detail?problem_id=1047
Description
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAXN 1111
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;
char s1[MAXN], s2[MAXN];
int LCS(char *s1, char *s2)
{
int L1 = strlen(s1), L2 = strlen(s2);
int* c = new int[L2];
int begin, end = 0, len = 0;
for(int i=0; i<L1; i++) {
for(int j=L2-1; j>=0; j--) {
if(s1[i] == s2[j]) {
if(i==0 && j==0) c[j] = 1;
else c[j] = c[j-1] + 1;
}else c[j] = 0;
if(c[j] > len) {
len = c[j];
end = j;
}
}
}
return len;
/*
char* pos = new char[len+1];
begin = end - len + 1;
for(int i=begin; i<end; i++) {
pos[i-begin] = s2[i];
}
pos[len] = '\0';
return pos;
*/
}
int main()
{
int cas;
scanf("%d", &cas);
getchar();
while(cas--) {
scanf("%s %s", s1, s2);
printf("%d\n", LCS(s1, s2));
}
return 0;
}
