首页 > 专题系列 > Java解POJ > POJ 1226 Substrings [解题报告] Java
2013
11-09

POJ 1226 Substrings [解题报告] Java

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

解题代码:

//* @author:alpc12
import java.math.*;
import java.io.*;
import java.util.*;

class Main {
 public static void main(String[] args) throws Exception {
	new Main().run();
 }

 private int n;	

 private void run() throws Exception {
  Scanner cin = new Scanner(System.in);
  int ntc = cin.nextInt(),i,j,k;
  while(ntc-- != 0) {
	n = cin.nextInt();
	StringBuffer[] s = new StringBuffer[n];
	for(i = 0; i < n; ++i) {
		s[i] = new StringBuffer(cin.next());
	}
	int max = 0;
	for(i = 0; i < s[0].length(); ++i) {
	  for(j = i+1; j <= s[0].length(); ++j) {
	    if(check(s,i,j)) {
		  max = Math.max(max,j-i);
	    }
	 }
	}
	System.out.println(max);
   }
}
	
boolean check(StringBuffer s[], int x, int y) {
  int i;
  String pattern1 = s[0].toString().substring(x, y);
  String pattern2 = "";
  for(i = pattern1.length()-1; i >= 0; --i) {
	pattern2 += pattern1.charAt(i);
  }
  for(i = 0; i < n; ++i) {
	if(s[i].toString().indexOf(pattern1) == -1
		&& s[i].toString().indexOf(pattern2) == -1) {
		return false;
	}
  }
  return true;
 }
}

  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。