Monday, May 28, 2012

Linear time algorithm for finding longest palindrome substring


Linear time algorithm for finding 

longest palindrome substring


Code in C++

char str[MAXSIZE];//pre-processed array
int p[MAXSIZE]; //auxiliary array
char s[MAXSIZE];//original input
int n;

void populatep()
{
    int i;
    int mx = 0;
    int id;
    for(i=1; i<n; i++)
    {
        if( mx > i )
            p[i] = MIN( p[2*id-i], p[id]+id-i );
        else
            p[i] = 1;
        for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
            ;
        if( p[i] + i > mx )
        {
            mx = p[i] + i;
            id = i;
        }
    }
}

void preprocess()
{
    int i,j,k;
    n = strlen(s);
    str[0] = '$';
    str[1] = '#';
    for(i=0;i<n;i++)
    {
        str[i*2 + 2] = s[i];
        str[i*2 + 3] = '#';
    }
    n = n*2 + 2;
    str[n] = 0;
    cout <<str<<" : "<<strlen(str)<<endl;
}

void getlength()
{
    int i;
    int ans = 0;
    for(i=0;i<n;i++)
        getmax(ans, p[i]);
    printf("%d\n", ans-1);
}
//test
int main()
{
    while( canf("%s", s) )
    {
        preprocess();
        populatep();
        getlength();
    }
    return 0;
}


For background, please read Wikipedia’s article about Longest Palindromic Substring.

How To Read C Declarations


Even experienced C programmers have difficulty reading declarations that go beyond simple arrays and pointers. For example, is the following an array of pointers or a pointer to an array?
int *a[10];
What the heck does the following mean?
int (*(*vtable)[])();
Naturally, it's a pointer to an array of pointers to functions returning integers(wink)
This short article tells you how to read any C declaration correctly using a very simple technique. I am 99% certain that I read this in a book in the late 1980s, but I can't remember where. I doubt that I discovered this on my own (even though I've always been delighted by computer language structure and esoterica). I do remember, however, building a simple program that would translate any declaration into English.

The golden rule

The rule goes like this:
Start at the variable name (or innermost construct if no identifier
is present. Look right without jumping over a right parenthesis; say
what you see. Look left again without jumping over a parenthesis; say
what you see. Jump out a level of parentheses if any. Look right;
say what you see. Look left; say what you see. Continue in this
manner until you say the variable type or return type.
The degenerate case is:
int i;
Starting at i , you look right and find nothing. You look left and find the type int , which you say. Done.
Ok, now a more complicated one:
int *a[3];
Start at a . Look right, say array of size 3. Look left and say pointer. Look right and see nothing. Look left and say int. All together you say a is an array of size 3 pointers to int.
Adding parentheses is when it gets weird:
int (*a)[3];
The parentheses change the order just like in an expression. When you look right after a , you see the right parenthesis, which you cannot jump over until you look left. Hence, you would say a is a pointer to an array of 3 ints.

Function pointers

The C "forward" declaration:
extern int foo();
just says that foo is a function returning int. This follows the same pattern for reading declarators as you saw in previous section. Start at foo and look right. You see () so say function. You look left and see int . Say int.
Now, try this one:
extern int *foo();
Yep, you say foo is a function returning a pointer to int.
Now for the big leap. Just like we can make a pointer to an int or whatever, let's make a pointer to a function. In this case, we can drop the extern as it's no longer a function forward reference, but a data variable declaration. Here is the basic pattern for function pointer:
int (*foo)();
You start at foo and see nothing to the right. So, to the left, you say pointer. Then to the right outside you see function. Then left you see int . So you say foo is a pointer to a function returning int.

Combinations

Here is an array of pointers to functions returning int, which we'll need for vtables below:
int (*Object_vtable[])();
You need one last, incredibly bizarre declaration, for the lab:
int (*(*vtable)[])();
This is the pointer to the vtable you will need in each "object" you define.
This pointer to a vtable is set to the address of a vtable; for example, &Truck_vtable .

Summary

The following examples summarize the cases needed for building virtual tables ala C++ to implement polymorphism (like the original cfront C++ to C translator).
int *ptr_to_int;
int *func_returning_ptr_to_int();
int (*ptr_to_func_returning_int)();
int (*array_of_ptr_to_func_returning_int[])();
int (*(*ptr_to_an_array_of_ptr_to_func_returning_int)[])();
                                                                                                  Source: click here   Author Terence Parr



The great advice from John Bode

It's easier to remember the rule as absent any explicit grouping, () and [] bind before *. Thus, for a declaration like
T *a[N];
the [] bind before the *, so a is an N-element array of pointer. Breaking it down in steps:
   a     -- a
   a[N]  -- is an N-element array
  *a[N]  -- of pointer
T *a[N]  -- to T.
For a declaration like
T (*a)[N];
the parens force the * to bind before the [], so
    a      -- a
  (*a)     -- is a pointer
  (*a)[N]  -- to an N-element array
T (*a)[N]  -- of T
It's still the clockwise/spiral rule, just expressed in a more compact manner.