AlgorithmsLibrary/PalindromeTree.cpp at master · PawanAIT/AlgorithmsLibrary · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mp make_pair
#define pb push_back
#define mt make_tuple
#define LD long double
#define gc getchar_unlocked
#define pc putchar_unlocked
#define MOD 1000000007
#define MAXN 1000500
#define bitcount _builtin_popcount
#define INF 2000000000
#define EPS 1e-9

template<typename T>T absll(T X)
{
    if(X<0)
        return -1*X;
    else
        return X;
}

struct node
{
	int next[26];
	int len;
	int sufflink;
	int num;
};

int len;
char str[MAXN];
node tree[MAXN];
int num;		// node 1 - root with len -1, node 2 - root with len 0
int suff;		// max suffix palindrome
LL ans;

bool addLetter(int pos)
{
	int cur=suff,curlen=0;
	int let=str[pos]-'a';

	while(true)
	{
		curlen=tree[cur].len;
		if((pos-1-curlen>=0)&&(str[pos-1-curlen]==str[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(true)
	{
		cur=tree[cur].sufflink;
		curlen=tree[cur].len;
		if((pos-1-curlen)>=0&&(str[pos-1-curlen]==str[pos]))
		{
			tree[num].sufflink=tree[cur].next[let];
			break;
		}
	}

	tree[num].num=1+tree[tree[num].sufflink].num;
	return true;
}

void initPalindromeTree()
{
	num=2;
	suff=2;
	tree[1].len=-1;
	tree[1].sufflink=1;
	tree[2].len=0;
	tree[2].sufflink=1;
}

int main()
{
	gets(str);
	len=strlen(str);

	initPalindromeTree();
	//ans counts the number of total palindromes
	for(int i=0;i<len;i++)
	{
		addLetter(i);
		ans+=tree[suff].num;
	}
	cout<<ans<<endl;
	return 0;
}