HDU 1238 Substrings（暴力+stl）

刺骨的言语ヽ痛彻心扉 2022-06-08 22:44 132阅读 0赞

You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.

Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.

Output

There should be one line per test case containing the length of the largest string found.

Sample Input

2
    3
    ABCD
    BCDFF
    BRCD
    2
    rose
    orchid

Sample Output

2
    2

题解：

给你n个串，让你找这些串的最长公共子串

直接找出最短的串，枚举他的所有子串，然后暴力遍历，stl很方便，就是也有一些坑，莫名其妙不知道错哪

不过stl用起来很慢，不然c风格的字符串。。

虽然我没用到一个函数，但是还是学习一下

包含文件：string.h

函数名: strstr  
函数原型：extern char \*strstr(char \*str1, char \*str2);  
功能：找出str2字符串在str1字符串中第一次出现的位置（不包括str2的串结束符）。

如果没找到就会返回NULL

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    int vis[20005];
    int cmp1(string x,string y)//从小到大
    {
        return x.size()<y.size();
    }
    int cmp2(string x,string y)//从大到小
    {
        return x.size()>y.size();
    }
    int main()
    {
        int test,n,i,j,k,cent,d,len,tot;
        scanf("%d",&test);
        while(test--)
        {
            string p[105],ss[20005];
            scanf("%d",&n);
            cent=0;
            for(i=0;i<n;i++)
            {
                cin>>p[i];
                vis[i]=0;
            }
            sort(p,p+n,cmp1);
            for(i=0;i<p[0].size();i++)//枚举子串
            {
                for(j=1;i+j<p[0].size()+1;j++)
                {
                    ss[cent]=p[0].substr(i,j);
                    cent++;
                    tot=0;
                    for(k=ss[cent-1].size()-1;k>=0;k--,tot++)
                    {
                        ss[cent].push_back(ss[cent-1][k]);
                    }
                    cent++;
                }
            }
            sort(ss,ss+cent,cmp2);
            cent=unique(ss,ss+cent)-ss;//可以去一下重
            len=0;
            for(i=0;i<cent;i++)
            {
                int tag=1;
                for(j=1;j<n;j++)
                {
                    if(p[j].find(ss[i])==string::npos)//如果没找到
                    {
                        tag=0;
                        break;
                    }
                }
                if(tag)
                {
                    len=ss[i].size();
                    break;
                }
            }
            printf("%d\n",len);
        }
        return 0;
    }