题目链接
本题可直接使用暴力求解,找出输入的字符串中最短的字符串,因为最大公共子串的长度不会超过它的长度。以它为基础,不断构造(枚举)它的子串,判断该子串或该子串的反串是否也是其它字符串的子串,若是则比较当前已有的最大长度比较,记录较大者。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
//输入的多个字符串
char a[105][105];
//用于装截取的字符串
char b[105];
int main()
{
int t, n, i, j, k, min_len, index;
int flag = 1, p, max = 0;
scanf("%d", &t);
while(t--){
//公共子串的最大长度
max = 0;
memset(a, 0, sizeof(a));
//min_len用于记录输入的多个字符串中的最短的字符串的长度
//由于题目所给字符串长度不大于100,故只要保证min_len大于100即可
min_len = 10000;
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%s", a[i]);
//记录最短字符串的长度和下标
if(min_len > strlen(a[i])){
min_len = strlen(a[i]);
index = i;
}
}
//暴力截取子字符串
//前两个循环为截取的位置,即[i,j],第三个for构造子字符串
for(i = 0; i < min_len; i++){
for(j = i; j < min_len; j++){
for(k = i; k <= j; k++){
//构造的子串记录在b中
b[k-i] = a[index][k];
}
//结束标志设置
b[j-i+1] = '\0';
//flag用于标记是否是所有字符串的公共子串
flag = 1;
//除开最短的一个字符串,依次比较其他字符串,看是否包含子串b或者b的反串
for(p = 0; p < n; p++){
if(p != index && !strstr(a[p], b) && !strstr(a[p], strrev(b))){
flag = 0;
break;
}
}
//若有更长的子串则记录
if(strlen(b) > max && flag == 1)
max = strlen(b);
}
}
printf("%d\n", max);
}
return 0;
}
网友评论