最大公共子序列和最大公共子串

最大公共子序列

最大公共子串

动态规划（未优化）

动态规划（一级空间优化）

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

char s1[1000001], s2[1000001];
int dp[2][1000005];

int lcs() {
	int len1 = strlen(s1), len2 = strlen(s2);
	int i, j, cur = 1, pre = 0, cnt = 0;
	if(len2 > len1) {
		for(i = 0; i <= len2; i++) dp[0][i] = 0;
		dp[1][0] = 0;
		for(i = 1; i <= len1; i++) {
			for(j = 1; j <= len2; j++) {
				if(s1[i - 1] == s2[j - 1]) {
					dp[cur][j] = dp[pre][j - 1] + 1;
					cnt = max(cnt, dp[cur][j]);
				}
				else dp[cur][j] = 0;
			}
			swap(cur, pre);
		}
		return cnt;
	}
	else {
		for(i = 0; i <= len1; i++) dp[0][i] = 0;
		dp[1][0] = 0;
		for(i = 1; i <= len2; i++) {
			for(j = 1; j <= len1; j++) {
				if(s2[i - 1] == s1[j - 1]) {
					dp[cur][j] = dp[pre][j - 1] + 1;
					cnt = max(cnt, dp[cur][j]);
				}
				else dp[cur][j] = 0;
			}
			swap(cur, pre);
		}
		return cnt;
	}
}

int main() {
	while(~scanf("%s%s", s1, s2)) {
		int ans = lcs();
		printf("%d\n", ans);
	}
	return 0;
}

动态规划（二级空间优化）

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

char s1[1000001], s2[1000001];
int dp[1000001];

int lcs() {
	int len1 = strlen(s1), len2 = strlen(s2);
	int i, j, tmp, old, cnt = 0;
	if(len2 > len1) {
		for(i = 0; i <= len2; i++) dp[i] = 0;
		for(i = 1; i <= len1; i++) {
			old = dp[0];
			for(j = 1; j <= len2; j++) {
				tmp = dp[j];
				if(s1[i - 1] == s2[j - 1]) {
					dp[j] = old + 1;
					cnt = max(cnt, dp[j]);
				}
				else dp[j] = 0;
				old = tmp;
			}
		}
		return cnt;
	}
	else {
		for(i = 0; i <= len1; i++) dp[i] = 0;
		for(i = 1; i <= len2; i++) {
			old = dp[0];
			for(j = 1; j <= len1; j++) {
				tmp = dp[j];
				if(s2[i - 1] == s1[j - 1]) {
					dp[j] = old + 1;
					cnt = max(cnt, dp[j]);
				}
				else dp[j] = 0;
				old = tmp;
			}
		}
		return cnt;
	}
}

int main() {
	while(~scanf("%s%s", s1, s2)) {
		int ans = lcs();
		printf("%d\n", ans);
	}
	return 0;
}