This problem is from today's atcoder beginner contest

You are given a list A of lowercase English strings.
For each string S in A, solve the following problem:

You can perform two operations to S:

- Delete the last character of S (if it is non-empty)
- Add any lowercase character to the end of S

Find the minimum number of operations to convert S into either the empty string or a string that comes before it in A.

This kind of screams trie:

The conversion cost between two strings is essentially equal to the sum of their lengths, minus their prefix overlap (times two). So, for each string, use some sort of datastructure to match prefixes with the strings that come before them, and find which of these strings have the minimal length, etc.

Trie is perfect for this because we can, while iterating through the list of input strings, mantain a trie of all processed strings. Then we can traverse this trie to see how much of the currently processing string matches the previous strings.

And, if we encode in each trie node the minimum length string that is "encompassed" by that node, we can for each prefix of the current string see the optimal cost when "stopping" at that prefix.

I had never used trie before so this implementation was somewhat improvised, but it works!

#include <iostream>
#include <string>

struct trie{
    int minlen = 0;
    trie *next[26] = {};
};

trie root;

int main(){
    int n; std::cin >> n;

    while(n--){
        std::string s; std::cin >> s;

        trie *now = &root;

        // matches root -> traverse along until no avail
        int i, best = s.length();
        for(i=0; i<s.length(); ++i){
            if(now -> next[s[i]-'a'] != 0){
                now = now -> next[s[i]-'a'];
                best = std::min(best, (int)s.length() - i + (now -> minlen) - i - 2);
                now -> minlen = std::min(now -> minlen, (int)s.length());
            }else break;
        }

        std::cout << best << '\n';

        // build up trie
        for(; i<s.length(); ++i){
            now -> next[s[i]-'a'] = new trie;
            now = now -> next[s[i]-'a'];
            now -> minlen = s.length();
        }
    }
}

tags: programming atcoder contest-logs