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