Q:

Longest prefix string length for all the suffixes

Find the length of the longest prefix string for all the suffixes of the string. 
For example suffixes of the string ababaa are ababaa, babaa, abaa, baa, aa and a. The similarities of each of these strings with the string "ababaa" are 6,0,3,0,1,1 respectively. Thus the answer is 6 + 0 + 3 + 0 + 1 + 1 = 11.
I wrote following code 
#include <iostream>
#include <string.h>

#include <stdio.h>
#include <time.h>

int main ( int argc, char **argv) {
    size_t T;
    std::cin >> T;
    char input[100000];
    for ( register size_t i = 0; i < T; ++i) {
        std::cin >> input;

        double t = clock();

        size_t len    = strlen(input);
        char *left    = input;
        char *right   = input + len - 1;
        long long sol = 0;
        int end_count = 1;
        while ( left < right ) {
            if ( *right != '\0') {
                if ( *left++ == *right++ ) {
                    sol++;
                    continue;
                }
            }
            end_count++;
            left = input; // reset the left pointer
            right = input + len - end_count; // set right to one left.
        }
        std::cout << sol + len << std::endl;
        printf("time= %.3fs\n", (clock() - t) / (double)(CLOCKS_PER_SEC));
    }
}

Working fine, but for a string which is 100000 long and having same character i.e. aaaaaaaaaa.......a, it is taking long time , how can i optimize this one more.

A:

You can use Suffix Array: http://en.wikipedia.org/wiki/Suffix_array

