# Rikka with Nickname （简单题）

2018/08/19 21:25

Rikka with Nickname

64bit IO Format: %lld

Sometimes you may want to write a sentence into your nickname like "lubenwei niubi". But how to change it into a single word? Connect them one by one like "lubenweiniubi" looks stupid. To generate a better nickname, Rikka designs a non-trivial algorithm to merge a string sequence s1...sn into a single string. The algorithm starts with s=s1 and merges s2...sn into s one by one. The result of merging t into s is the shortest string r which satisfies s is a prefix of r and t is a subsequence of r.(If there are still multiple candidates, take the lexicographic order smallest one.) String s is a prefix of r if and only if |s| ≤ |r| and for all index i ∈ [1, |s|], si = ri. String s is a subsequence of r if and only if there is an index sequence which satisfies . For example, if we want to generate a nickname from "lubenwei niubi", we will merge "niubi" into "lubenwei", and the result is "lubenweiubi". Now, given a sentence s1...sn with n words, Rikka wants you to calculate the resulting nickname generated by this algorithm.

The first line contains a single number t(1 ≤ t ≤ 3), the number of testcases.For each testcase, the first line contains one single integer n(1 ≤ n ≤ 106).Then n lines follow, each line contains a lowercase string .

For each testcase, output a single line with a single string, the result nickname.

2
2
lubenwei
niubi
3
aa
ab
abb

lubenweiubi
aabb

``````#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const ll mod=998244353;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define MAX 100005
int T;
int n;
string s,ans,t,ss;
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin>>T;
while(T--)
{
cin>>n;
cin>>s;
ans=s;
for(int d=0;d<n-1;d++)
{
t=ans;
cin>>s;
int k=0;
for(int i=0;i<s.size();i++)
{
int tt=t.find(s[i]);
if(tt>=0)
{
k++;
tt++;
t.erase(0,tt);
}
else break;
}
for(int j=k;j<s.size();j++)
ans+=s[j];
}
cout<<ans<<endl;
}
return 0;
}``````

``````#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const ll mod=998244353;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define MAX 100005
int T;
int n;
string s,ans,t,ss;
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin>>T;
while(T--)
{
cin>>n;
cin>>s;
ans=s;
for(int d=0;d<n-1;d++)
{
t=ans;
cin>>s;
int k=0;
int f=0;
while(k<t.size())
{
if(s[f]==t[k])f++,k++;
else k++;
if(f==s.size())
break;
}
for(int j=f;j<s.size();j++)
ans+=s[j];
}
cout<<ans<<endl;
}
return 0;
}``````

0
0 收藏

0 评论
0 收藏
0