当前位置：首页 > news >正文

POJ 1226 Substrings 解题报告

news 来源：原创 2024/4/30 22:00:45

1.链接地址：http://poj.org/problem?id=1226

2.题目：

Substrings

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 10252 Accepted: 3519

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 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 
Source

Tehran 2002 Preliminary

3.代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string.h>
 6 using namespace std;
 7 const int NUM = 100;
 8 char strs[NUM][NUM + 1];
 9 int main()
10 {
11     //freopen("F:\\input.txt","r",stdin);
12     
13     int t;
14     cin>>t;
15     
16     int n,length;
17     while(t--)
18     {
19         cin>>n;
20         cin.get();
21         
22         for(int i = 0; i < n; i++)
23         {
24             scanf("%s",strs[i]);
25         }
26         
27         for(int i = 0; i < n; i++)
28 
29         length = strlen(strs[0]);
30         char substr[NUM + 1],substr2[NUM + 1];
31         int res = 0;
32         for(int i = 1; i <= length; i++)
33         {
34             for(int j = 0; (j+i-1) < length; j++)
35             {
36                 strncpy(substr,&strs[0][j],i);
37                 substr[i] = '\0';
38                 strcpy(substr2,substr);
39                 
40                 for(int k = 0; k < (i+1)/2; k++)
41                 {
42                     char tmp = substr2[k];
43                     substr2[k] = substr2[i-1-k];
44                     substr2[i-1-k] = tmp;
45                 }
46                 
47                 
48                 //cout<<"substr="<<substr<<",substr2="<<substr2<<endl;
49                 int k;
50                 for(k = 1; k < n; k++)
51                 {
52                     if(!strstr(strs[k],substr) && !strstr(strs[k],substr2)) break;
53                 }
54                 if(k >= n ) 
55                 {
56                     res = i;
57                     break;
58                 }
59             }
60         }
61         
62         cout<<res<<endl;
63     }
64     return 0;
65 }