美文网首页
杭电oj-1238-Substrings

杭电oj-1238-Substrings

作者: Fgban | 来源:发表于2019-12-17 16:43 被阅读0次

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

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

    相关文章

      网友评论

          本文标题:杭电oj-1238-Substrings

          本文链接:https://www.haomeiwen.com/subject/cptenctx.html