HDU 1238 Substring

阳光穿透心脏的1/2处 2022-09-30 06:03 110阅读 0赞

Substrings

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 10192 Accepted Submission(s): 4845

Problem Description  
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

Author  
Asia 2002, Tehran (Iran), Preliminary

Recommend  
Eddy

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <algorithm>
    #include <set>
    #include <vector>
    using namespace std;
    string s[105];
    vector<int>v;
    bool cmp(string a,string b)
    {
        return a.length()<b.length();
    }
    int dfs(string &str,int n)
    {
        int len=str.length();
         int flag=1;
         for(int i=len;i>=1;i--){
       //倒序求最长子串
             for(int j=0;i+j<=len;j++){
                 string temp=str.substr(j,i);
                 string t=temp;
                 string retemp=t.assign(t.rbegin(),t.rend());//赋以新值逆向迭代器
                 for(int k=1;k<n;k++){
                     if(s[k].find(temp)==-1&&s[k].find(retemp)==-1){
                         flag=0;
                         break;
                     }
                 }
                 if(flag)return temp.length();
                 flag=1;
             }
         }
         return 0;
    }
    int main()
    {
        int t;
        cin>>t;
    
        while(t--)
        {
            int n;
            cin>>n;
            for(int i=0;i<n;i++)
            {
                cin>>s[i];
            }
            sort(s,s+n,cmp);
            int ans = dfs(s[0],n);
            cout<<ans<<endl;
        }
        return 0;
    }