String Similarity

gistfile1.txt

long stringSimilarity(string s) {
    long res = (long)s.length();
    vector<long> subCounts(s.length());
    vector<int> backRefs(s.length());
    subCounts[0] = 0;
    bool onRun = false;
    int runStart = 0;
    for (int j = 1; j < s.length(); j++) {
        if (onRun) {
            backRefs[j] = j - runStart;
            if (s[j - runStart] == s[j]) {
                subCounts[j] = subCounts[j - runStart] + 1L;
            } else {
                int backJ = backRefs[j - 1];
                while (backJ != 0 && backJ != -1 && s[backJ + 1] != s[j]) {
                    backJ = backRefs[backJ];
                }
                if (backJ != -1 /*&& backJ != 0*/ && s[backJ + 1] == s[j]) {
                    runStart = j - (backJ + 1);
                    backRefs[j] = j - runStart;
                    subCounts[j] = subCounts[j - runStart] + 1L;
                } else {
                    onRun = false;
                }
            }
        }
        if (!onRun && s[j] == s[0]) {
            onRun = true;
            runStart = j;
            subCounts[j] = 1L;
            backRefs[j] = 0;
        }
        if (!onRun) {
            subCounts[j] = 0L;
            backRefs[j] = -1;
        }
    }
    return res + accumulate(subCounts.begin(), subCounts.end(), 0L);
}