POJ 1226 Substrings

問題
http://poj.org/problem?id=1226

解法
全探索したら通った。最小の文字列を選んで計算回数を落としたが別に必要ないっぽい。

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

int t, n;

int main(){
	cin >> t;
	for(;t > 0; t--){
		cin >> n;
		string str[n];
		int min_len = 101;
		int min_idx;
		for(int i = 0; i < n; i++){
			cin >> str[i];
			if(min_len > str[i].size()){
				min_len = str[i].size();
				min_idx = i;
			}
		}
		int xam = 0;
		for(int i = 0; i < str[min_idx].size(); i++){
			for(int l = str[min_idx].size() - i; l > xam; l--){
				string sub = str[min_idx].substr(i, l);
				string inv = sub; reverse(inv.begin(), inv.end());
				bool f = true;
				for(int j = 0; j < n; j++)
					if(str[j].find(sub) == string::npos && str[j].find(inv) == string::npos)
						f = false;
				if(f) xam = l;
			}
		}
		cout << xam << endl;
	}
}