杭电oj-1238-Substrings

题目链接
本题可直接使用暴力求解，找出输入的字符串中最短的字符串，因为最大公共子串的长度不会超过它的长度。以它为基础，不断构造（枚举）它的子串，判断该子串或该子串的反串是否也是其它字符串的子串，若是则比较当前已有的最大长度比较，记录较大者。

#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;
}