PS
My straightforward C++ solution got TLE...
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
//freopen("88.txt", "rt", stdin);
//freopen("99.txt", "wt", stdout);
int tcs;
string s;
cin >> tcs;
while (tcs-- > 0) {
cin >> s;
int n = s.size();
s = s + ' ';
vector< vector<int> > a(256);
int ans = 0;
for (int i = n - 1; i >= 0; --i) {
int lev = 0;
vector<int> p = a[s[i]];
vector<int> q;
while (!p.empty()) {
q.clear();
++lev;
for (int j = 0; j < p.size(); ++j) {
if (s[p[j] + 1] == s[i + lev]) {
q.push_back(p[j] + 1);
}
}
p.swap(q);
}
a[s[i]].push_back(i);
ans += n - i - lev;
}
cout << ans << endl;
}
return 0;
}
--
http://mail.python.org/mailman/listinfo/python-list
