SPOJ Number of Palindromes(回文树)

Time Limit: 100MS

Memory Limit: 1572864KB

64bit IO Format: %lld & %llu

Description

Each palindrome can be always created from the other palindromes, if a single character is also a palindrome. For example, the string "malayalam" can be created
by some ways:

* malayalam = m + ala + y + ala + m

* malayalam = m + a + l + aya + l + a + m

We want to take the value of function NumPal(s) which is the number of different palindromes that can be created using the string S by the above method. If the same palindrome occurs more than once then all of them should be counted separately.

Input

The string S.

Output

The value of function NumPal(s).

Limitations

0 < |s| <= 1000

Example

Input:

malayalam

Output:

Hint

Added by:	The quick brown fox jumps over the lazy dog
Date:	2010-10-18
Time limit:	0.100s-0.170s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All
Resource:	Udit Agarwal

回文树：

参考大牛的博客：http://blog.****.net/lwfcgz/article/details/48739051

回文树是一种处理回文串的强大工具

#include <iostream>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

#include <math.h>

#include <stdio.h>

using namespace std;

#define MAX 1005

struct Node

{

    int next[26];

    int len;

    int sufflink;

    int num;

}tree[MAX];

char s[MAX];

int num;

int suff;

bool addLetter(int pos)

{

    int cur=suff,curlen=0;

    int let=s[pos]-'a';

    while(1)

    {

        curlen=tree[cur].len;

        if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])

            break;

        cur=tree[cur].sufflink;

    }

    if(tree[cur].next[let])

    {

        suff=tree[cur].next[let];

        return false;

    }

    num++;

    suff=num;

    tree[num].len=tree[cur].len+2;

    tree[cur].next[let]=num;

    if(tree[num].len==1)

    {

        tree[num].sufflink=2;

        tree[num].num=1;

        return true;

    }

    while(1)

    {

        cur=tree[cur].sufflink;

        curlen=tree[cur].len;

        if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])

        {

            tree[num].sufflink=tree[cur].next[let];

            break;

        }

    }

    tree[num].num=1+tree[tree[num].sufflink].num;

    return true;

}

void initTree()

{

    num=2;suff=2;

    tree[1].len=-1;tree[1].sufflink=1;

    tree[2].len=0;tree[2].sufflink=1;

}

int main()

{

    scanf("%s",s);

    int len=strlen(s);

    initTree();

    long long int ans=0;

    for(int i=0;i<len;i++)

    {

         addLetter(i);

         ans+=tree[suff].num;

    }

    printf("%d\n",ans);

    return 0;

}

Number of Palindromes