Định nghĩa vẻ đẹp một cặp xâu là \(min(l_p,l_s)^2\).

Ta cần tính tiền tố và hậu tố cùng một lúc trên Trie. Để làm được điều này, ta sẽ sử dụng một Node trên cây là đại diện cho một từ ghép hai ký tự tiền tố và hậu tố lại với nhau. Vì vậy, bộ tự điển lúc này sẽ là \(26 \times 26 = 676\) ký tự. \((Node* child[26][26])\).

Ví dụ: khi thêm chuỗi "abcd" vào cây. Sẽ đi qua lần lượt các Node là \(ad \rightarrow bc \rightarrow cb \rightarrow da\). Nếu số lượng đi qua Node \(ad\) là \(3\) thì có nghĩa là có \(3\) xâu có cùng tiền tố và hậu tố là \(a\) và \(d\)

Tới đây, bài toán quy về tìm tổng bình phương độ dài tiền tố của các cặp xâu thì bài toán có thể dễ dàng được giải quyết bằng cách dfs trên trie các xâu đã cho.