Packing Words
National Olympiad — Regional round
Submission name: packing.cpp
Problem summary
Combine the supplied words in their given order by sharing equal suffix/prefix portions. For successive occurrences, both the starting and ending position of the new word must be strictly greater than those of the preceding word. Use the largest permitted overlap at each join.
Input
N, followed by N lowercase Latin words.
Output
The packed string.
Constraints
1 ≤ N ≤ 128; each word has length 1…64.
Worked example
An independently prepared example for this explanation.
Input
3 abcd cde def
Output
abcdef
Solution analysis
- For adjacent words A,B test overlaps k from min(|A|,|B|)−1 down to 0.
- The strict bound ensures neither the previous start nor its end is retained by the next occurrence.
- Append the nonoverlapping suffix of B at the first match. Earlier packed characters cannot alter an overlap between these adjacent occurrences.
Why it works
An admissible overlap must be a suffix of A and prefix of B, shorter than both words. Choosing its maximum places B as early as permitted. All later relative offsets depend only on adjacent words, so these local choices give the packed result.
Watch out. A whole-word overlap is forbidden even when one word is a suffix or prefix of the other.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
#include<string>
#include<iterator>
using namespace std;
int main(){
int n;
cin>>n;
string prev,result;
cin>>prev;
result=prev;
for(int i=1;i<n;i++){
string next;
cin>>next;
int k=min(prev.size(),next.size())-1;
while(k>0&&prev.substr(prev.size()-k)!=next.substr(0,k)){
k--;
}
result+=next.substr(k);
prev=next; // Retain adjacent-word boundaries.
}
cout<<result<<'\n';
}