POJ 1226 Substrings 문제 풀이 보고서

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 }

4. 사고방식:
1. 가능 한 모든 문자열 을 옮 겨 다 니 며 일치 하 는 지 찾 습 니 다.효율 이 보통 나 쁜 것 은 아니 지만, 이것 에 대처 하 는 것 은 간단 해도 괜찮다.
2. 책 에서 추천 하 는 strrev 를 보 았 지만 G +, C + + 는 이 함수 가 없습니다.