Russian Qt Forum

Всем привет. Вот такая задача есть. Найти количество повторяющихся подстрок можна за O(n*n) с помощью Кнута-Пратта.
http://acmpskov.mybb.ru/viewtopic.php?id=27

C++ (Qt)
 
void duplicateFrequncyPair (string s, int& dupCount, double& frequency)
{  s = "thefoxfox";
    int n = s.length();
    int subCount = n * (n+1) /2;//substrings count
    int dupCount = subCount;//duplicates count
 
  for (int i = n; i > 0; --i)
    {
      string subs = s.substr(0, i);
      int length = subs.length();
      vector<int> pi = prefix_function(subs);
      dupCount-=(*max_element(pi.begin(), pi.end()));//unique count
    }
dupCount = subCount - dupCount;//duplicates now
frequency = dupCount / subCount;
}
 
vector<int> prefix_function (string s) {
        int n = (int) s.length();
        vector<int> pi (n);
        for (int i=1; i<n; ++i) {
                int j = pi[i-1];
                while (j > 0 && s[i] != s[j])
                        j = pi[j-1];
                if (s[i] == s[j])  ++j;
                pi[i] = j;
        }
        return pi;
}
 

Правильно ли я делаю?