HDU 1238 Substrings

Substrings
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8504 Accepted Submission(s): 3931
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

//   
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
using namespace std;
const int N=100+10;
int n,id,re,ilen;
char c[N][N];
int len[N];
int main(){
	int t,i,small,j,k,z,zz;
	bool ok;
	scanf("%d",&t);
	while(t--){
		re=0;
		small=N;
		scanf("%d",&n);
		for(i=0;i<n;i++){
		   	scanf("%s",c[i]);
		   	len[i]=strlen(c[i]);
		   	if(len[i]<small)
		   	  {
		   	  	small=len[i];
		   	  	id=i;
			}
		}
		ilen=len[id];
		for(i=ilen;re==0&&i>0;i--){   //      
		   for(j=0;re==0&&j+i-1<ilen;j++){   //           
		for(k=0;k<n;k++){
			if(k==id)
			continue;
			ok=0;
			for(z=0;z+i-1<len[k];z++) {  //     
			   for(zz=0;zz<i;zz++){
			   	   if(c[k][z+zz]!=c[id][j+zz])
			   	     break;
			   }
			   if(zz==i){
			   	ok=1;
			   	break;
			   }		  
		}	
		for(z=len[k]-1;!ok&&z-i+1>=0;z--) {  //     
			   for(zz=0;zz<i;zz++){
			   	   if(c[k][z-zz]!=c[id][j+zz])
			   	     break;
			   }
			   if(zz==i){
			   	ok=1;
			   	break;
			   }		  
		}
		  if(!ok)
		    break;	
		} 
		  if(k==n){
		  	re=i;
		  	break;
		  }		  
		} 	
} 
   	printf("%d
",re);
}
	return 0;
}



/*               AC  
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=100+10;
int n,id,re,ilen,rlen;
char c[N][N];
int len[N];
int main(){
	int t,i,small,j,k,z,zz;
	bool ok;
	scanf("%d",&t);
	while(t--){
		re=0;
		rlen=0;
		small=N;
		scanf("%d",&n);
		for(i=0;i<n;i++){
		   	scanf("%s",c[i]);
		   	len[i]=strlen(c[i]);
		   	if(len[i]<small)
		   	  {
		   	  	small=len[i];
		   	  	id=i;
			}
		}
		ilen=len[id];
		for(i=0;i<ilen;i++){  //              
		   for(j=ilen-i;i+j-1<ilen&&j>0;j--) {    //      
		      for(k=0;k<n;k++){   //        
		         if(k==id)
		        continue;
		      	  ok=0;
				for(z=0;z+j-1<len[k];z++){ //       
					for(zz=0;zz<j;zz++)  //       
					{
					    if(c[k][z+zz]!=c[id][i+zz])
						break;	
					}			
				  if(zz==j)
				   {
				      ok=1;
					  break;	
				   }		    
			  }
			  for(z=len[k]-1;!ok&&z-j+1>=0;z--){  //     
			  		for(zz=0;zz<j;zz++)
					{
					   	if(c[k][z-zz]!=c[id][i+zz])
						break;	
					}   
				   if(zz==j)
				   {
				      ok=1;
					  break;	
				   }	
			  } 
			  if(!ok)   //               
			  break;		  
		}
		if(k==n)
		{
		//                        ...     
			re=max(re,j);  
			break;
		 } 
}
}  
      printf("%d
",re); 
}
	return 0;
}
*/