首页 > ACM题库 > HDU-杭电 > HDU 1238 Substrings-字符串-[解题报告] C++
2013
12-04

HDU 1238 Substrings-字符串-[解题报告] C++

Substrings

问题描述 :

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.

输入:

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.

输出:

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

样例输入:

2
3
ABCD
BCDFF
BRCD
2
rose
orchid

样例输出:

2
2

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=1238

最主要的是要求字符串的子串,反串,直接用string;

#include<iostream>
 #include<algorithm>
 #include<string>
 using namespace std;
 int n;
 string s[111];
 
 int cmp(const string p,const string q){
     return p.length()<q.length();
 }
 
 int dfs(string &str){
     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;
     scanf("%d",&t);
     while(t--){
         scanf("%d",&n);
         for(int i=0;i<n;i++){
             cin>>s[i];
         }
         sort(s,s+n,cmp);
         int ans=dfs(s[0]);
         printf("%d\n",ans);
     }
     return 0;
 }

 


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks