文章

3

粉丝

137

获赞

2

访问

2.0k

头像
最大公共子串 题解:
P1855 兰州大学机试
发布于2024年2月19日 12:56
阅读数 640

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main() {
	char a[100];
	char b[100];
	int dp[100][100];
	gets(a);
	gets(b);

	int result = 0;
	int position = 0;
	
	for (int i = 0; i <= strlen(a); i ++) {
		dp[0][i] = 0;
	}
	for (int i = 0; i <= strlen(b); i ++) {
		dp[i][0] = 0;
	}

	for (int i = 0; i < strlen(a); i ++) {
		for (int j = 0; j < strlen(b); j ++) {
			if (a[i] != b[j]) {
				dp[i + 1][j + 1] = 0;
			} else {
				dp[i + 1][j + 1] = dp[i][j] + 1;
			}
			if (dp[i + 1][j + 1] > result) {
				position = i;
				result = dp[i + 1][j + 1];
			}
		}
	}

	if (result) {
		for (int i = position - result + 1;result --; i ++) {
			printf("%c", a[i]);
		}
	} else {
		printf("None");
	}
	
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发