You are given n n n strings s 1 , s 2 , … , s n s_1,s_2,…,s_n s1,s2,…,sn of length at most 8 8 8.
For each string s i s_i si, determine if there exist two strings s j s_j sj and s k s_k sk such that s i = s j + s k s_i=s_j+s_k si=sj+sk. That is, si is the concatenation of s j s_j sj and s k s_k sk. Note that j j j can be equal to k k k.
Recall that the concatenation of strings s s s and t t t is s + t = s 1 s 2 … s p t 1 t 2 … t q s+t=s_1s_2…s_pt_1t_2…t_q s+t=s1s2…spt1t2…tq, where p p p and q q q are the lengths of strings s s s and t t t respectively. For example, concatenation of “code” and “forces” is “codeforces”.
Input
The first line contains a single integer t ( 1 ≤ t ≤ 1 0 4 ) t (1≤t≤10^4) t(1≤t≤104) — the number of test cases.
The first line of each test case contains a single integer n ( 1 ≤ n ≤ 1 0 5 ) n (1≤n≤10^5) n(1≤n≤105) — the number of strings.
Then n lines follow, the i − t h i-th i−th of which contains non-empty string s i s_i si of length at most 8 8 8, consisting of lowercase English letters. Among the given n n n strings, there may be equal (duplicates).
The sum of n over all test cases doesn’t exceed 1 0 5 10^5 105.
Output
For each test case, output a binary string of length n n n. The i − t h i-th i−th bit should be 1 1 1 if there exist two strings s j s_j sj and s k s_k sk where s i = s j + s k s_i=s_j+s_k si=sj+sk, and 0 0 0 otherwise. Note that j j j can be equal to k k k.
Sample 1
Input
3
5
abab
ab
abc
abacb
c
3
x
xx
xxx
8
codeforc
es
codes
cod
forc
forces
e
code
Output
10100
011
10100101
首先这道题,要么拆要么组合。
不论是拆还是组合都要先读入所有的字符串,因为总不能还有字符串没读入你就说他能组成一个串吧。所以使用string类型数组来存。
之后思考是拆还是组,如果组的话就要枚举所有种组成的组合,最后肯定超时了。
如果拆也可以直接枚举,但是我们有更精妙的办法,就是利用substr(),这个函数传入的参数分别是启始位置和长度,如果我们标记上所有读入的字符串(可以用来组成的),然后枚举传入的长度参数,那么我们就可以取出来两段,前面一段后边一段,如果两段都是被标记的,那么就说明当前被枚举的字符串是可以被其他字符串组成的。
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
const int N = 1e5+10;
int n;
string str[N];
int main(){
int t;cin >> t;
while(t--){
map<string,bool>vis;
cin >> n;
for(int i = 1;i <= n;i++){
cin >> str[i];
vis[str[i]] = 1;
}
string a,b;
vector<int>ans(n+1); //存答案
for(int i = 1;i <= n;i++){
for(int j = 0;j < str[i].length();j++){
a = str[i].substr(0,j+1);
b = str[i].substr(j+1,str[i].length()-j-1);
if(vis[a] && vis[b]){
ans[i] = 1;
break;
}
}
}
for(int i = 1;i <= n;i++)cout << ans[i];
puts("");
}
return 0;
}