Hints

Good Pair

The described operations allow us to remove any prefix of a string, keep the next character, then remove some prefix of remaining part. For example, from \(12345678\) we can get \(378\) by removing \(12\), keeping \(3\) and removing \(456\).

Let’s take two strings \(S, T\) where \(S\) is longer than \(T\) and let \(k = |T|\). When should we count pair \((S, T)\) to the answer?

Lemma: Pair \((S, T)\) is good if the suffix of length \(k-1\) is same in both strings, and the first letter of \(T\) exists somewhere in the remaining prefix of \(S\).

Let’s actually reverse every string in order, which modifies the lemma:

Reversion Lemma: Pair \((S, T)\) is good if the first \(k-1\) characters are same in both strings, and the last letter of \(T\) exists somewhere in the remaining suffix of \(S\).

Solution

Let’s use TRIE (but you can also get AC with hashes).

For every string in the input, reverse it and then insert it in TRIE. Then, consider every string \(S\) to be the longer string in a pair: start from the end of a path representing this string, keep going up and maintain a set of already seen characters (those are characters existing in the suffix of \(S\)). When we visit a node \(v\), go through characters \(c\) in the set and look at vertex \(child[v][c]\) (TRIE vertex if we append \(c\) to the current node). If this child node exists and it’s the end of some string \(T\), we have a good pair and increase the answer by \(1\).

We could even print indices of all good pairs because the described algorithm finds them all, one by one. This also limits the answer to \(SumLengths \cdot 26\).

Time complexity \(O(SumLengths \cdot 26)\).

#include <bits/stdc++.h> // First Second, by Errichto
using namespace std;
const int nax = 1e6 + 5;
int child[nax][26];
bool is_end[nax];
int nxt = 1;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<string> in(n);
	vector<vector<int>> paths(n);
	for(int who = 0; who < n; ++who) {
		string& s = in[who];
		cin >> s;
		reverse(s.begin(), s.end());
		int node = 0;
		for(char ch : s) {
			paths[who].push_back(node);
			if(child[node][ch-'a'] == 0) {
				child[node][ch-'a'] = nxt++;
			}
			node = child[node][ch-'a'];
		}
		is_end[node] = true;
	}
	long long answer = 0; // 'int' is enough
	for(int who = 0; who < n; ++who) {
		string& s = in[who];
		set<char> suffix;
		for(int i = (int) s.length() - 1; i >= 0; --i) {
			suffix.insert(s[i]);
			int node = paths[who][i];
			for(char ch : suffix) {
				answer += is_end[child[node][ch-'a']];
			}
		}
	}
	printf("%lld\n", answer - n); // subtract pairs (s[i], s[i])
}