cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP C2015 · MediumString Segmentation

Restoring Word Boundaries

National Olympiad — National round

Submission name: dictionary.cpp

Solve in Editor →

Problem summary

Split a lowercase string into dictionary words, minimizing the number of words. Among such splits, minimize the first word length, then the second word length, and so on. A valid split exists.

Input

String; number n of dictionary entries; n lowercase words in alphabetical order.

Output

Minimum word count on the first line; the chosen words separated by single spaces on the second.

Constraints

1 ≤ n ≤ 2000; string length 1…100; word lengths 1…20.

Worked example

An independently prepared example for this explanation.

Input

aaaa
3
a
aa
aaa

Output

2
a aaa

Solution analysis

  1. Compute dp[i], the minimum word count for the suffix beginning at i, working right to left. Try every dictionary word matching there.
  2. Reconstruct from the left: choose the shortest matching word that preserves the optimal dp value.

Why it works

The suffix recurrence considers every first word of every split. Reconstruction chooses the minimum possible next length among globally optimal suffixes, yielding exactly the required lexicographic ordering of word lengths.

Complexity: O(n log n + length × n × maximum-word-length) time, O(length + dictionary-size) storage. Sorting the dictionary costs O(n log n); the dynamic program tries each word at each position.

Watch out. The tie-break is by length sequence, not alphabetical order.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: The suffix recurrence considers every first word of every split. Reconstruction chooses
// the minimum possible next length among globally optimal suffixes, yielding exactly the required
// lexicographic ordering of word lengths.
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iterator>
using namespace std;
int main(){
    string s;
    int n;
    cin>>s>>n;
    vector<string>w(n);
    for(auto&x:w){
        cin>>x;
    }
    sort(w.begin(),w.end(),[](auto&a,auto&b){
        return a.size()<b.size();
    });
    int m=s.size();
    vector<int>dp(m+1,1000000);
    dp[m]=0;
    for(int i=m-1;i>=0;i--){
        for(auto&x:w){
            if(i+(int)x.size()<=m&&s.compare(i,x.size(),x)==0){
                dp[i]=min(dp[i],1+dp[i+x.size()]);
            }
        }
    }
    cout<<dp[0]<<'\n';
    int i=0;
    while(i<m){
        for(auto&x:w){
            if(i+(int)x.size()<=m&&s.compare(i,x.size(),x)==0&&dp[i]==1+dp[i+x.size()]){
                if(i){
                    cout<<' ';
                }
                cout<<x;
                i+=x.size();
                break;
            }
        }
    }
    cout<<'\n';
}

Source: Arena Olimpiici ↗