POJ-3080 Blue Jeans---字符串+暴力

题目链接：

题目大意：

找最长的公共字串（长度>=3），长度相同就找字典序最小的

解题思路：

枚举第一个串的所以子串，处理出其他串的所有子串，然后set查找，更新ans

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 #include<string>
 5 using namespace std;
 6 int T;
 7 set<string>tot[12];
 8 int main()
 9 {
10     cin >> T;
11     while(T--)
12     {
13         int n;
14         string s, s1;
15         cin >> n;
16         cin >> s;
17         for(int i = 1; i < n; i++)
18         {
19             cin >> s1;
20             tot[i].clear();
21             for(int len = 3; len <= s1.size(); len++)
22             {
23                 for(int start = 0; start + len <= s1.size(); start++)
24                 {
25                     int end = start + len;
26                     string s2;
27                     for(int j = start; j < end; j++)
28                         s2 += s1[j];
29                     tot[i].insert(s2);
30                 }
31             }
32         }
33         string ans = "";
34         for(int len = 3; len <= s.size(); len++)
35         {
36             for(int start = 0; start + len <= s.size(); start++)
37             {
38                 int end = start + len;
39                 string s2;
40                 for(int i = start; i < end; i++)
41                     s2 += s[i];
42                 bool flag = 1;
43                 for(int i = 1; i < n; i++)
44                 {
45                     if(!tot[i].count(s2))
46                     {
47                         flag = 0;
48                         break;
49                     }
50                 }
51                 if(flag)
52                 {
53                     if(s2.size() > ans.size())
54                     {
55                         ans = s2;
56                     }
57                     else if(s2.size() == ans.size() && ans > s2)
58                     {
59                         ans = s2;
60                     }
61                 }
62             }
63         }
64         if(ans.size() < 3)cout<<"no significant commonalities"<<endl;
65         else cout<<ans<<endl;
66     }
67 }