POJ 1226 Substrings
2024-08-27 16:53:33
Substrings
Time Limit: 1000ms
Memory Limit: 10000KB
This problem will be judged on PKU. Original ID: 1226
64-bit integer IO format: %lld Java class name: Main
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 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
Source
解题:霸蛮好了。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define pii pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
string str[];
int main() {
int t,i,j,k,n;
bool flag;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i = ; i < n; i++)
cin>>str[i];
sort(str,str+n);
flag = false;
for(k = str[].length(); k; k--){
for(i = ; i + k <= str[].length(); i++){
string a = str[].substr(i,k);
string b(a.rbegin(),a.rend());
for(j = ; j < n; j++)
if(str[j].find(a) == - && str[j].find(b) == -) break;
if(j == n) {flag = true;break;}
}
if(flag) break;
}
flag?printf("%d\n",k):puts("");
}
return ;
}
最新文章
- Centos 7 在VBox下不能联网
- Kickstart/Anaconda实现自动化安装原理探究
- Android线程池(二)
- prim求MST
- Maven学习-构建项目
- centos6.5 scala环境变量
- 从Object.definedProperty中看vue的双向数据的绑定
- servlet什么时候被实例化?【转】
- 记一次<;iframe>;的使用
- MySQL 中触发器的应用
- VS Code 安装 C++ 调试环境
- [Micropython]TPYBoard v202 利用单片机快速实现家庭智能控制平台
- Nginx教程---01.Nginx入门
- hive orc update
- WCF 学习总结1 -- 简单实例
- spring security 非页面登录
- js switch case注意事项
- Session过期后自动跳转到登录页面
- js中的Math
- Qt录音机