Scribd
Upload
10 views2 pages

Palindrome Tree Implementation

The document contains a C++ implementation of a palindrome tree, which is a data structure designed to efficiently handle palindromes in strings. It includes a function to count the number of palindrome substrings in a given input string. The code is based on a specific problem from informatics.mccme.ru and is structured to initialize the tree and process the input string to calculate the result.

Uploaded by

kuldeep.jainit
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views2 pages

Palindrome Tree Implementation

The document contains a C++ implementation of a palindrome tree, which is a data structure designed to efficiently handle palindromes in strings. It includes a function to count the number of palindrome substrings in a given input string. The code is based on a specific problem from informatics.mccme.ru and is structured to initialize the tree and process the input string to calculate the result.

Uploaded by

kuldeep.jainit
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Personal Open source Business Explore Pricing Blog Support This repository Search Sign in Sign up

ADJA / algos Watch 20 Star 119 Fork 53

Code Issues 0 Pull requests 0 Pulse Graphs

Branch: master algos / Strings / [Link] Find file Copy path

ADJA Added palindrome tree 478a59f on Aug 28 2014

1 contributor

107 lines (85 sloc) 2.19 KB Raw Blame History

1 /**************************************************************************************
2
3 Palindrome tree. Useful structure to deal with palindromes in strings. O(N)
4
5 This code counts number of palindrome substrings of the string.
6 Based on problem 1750 from [Link]:
7 [Link]
8
9 **************************************************************************************/
10
11 #include <iostream>
12 #include <cstdio>
13 #include <cstdlib>
14 #include <algorithm>
15 #include <vector>
16 #include <set>
17 #include <map>
18 #include <string>
19 #include <utility>
20 #include <cstring>
21 #include <cassert>
22 #include <cmath>
23 #include <stack>
24 #include <queue>
25
26 using namespace std;
27
28 const int MAXN = 105000;
29
30 struct node {
31 int next[26];
32 int len;
33 int sufflink;
34 int num;
35 };
36
37 int len;
38 char s[MAXN];
39 node tree[MAXN];
40 int num; // node 1 - root with len -1, node 2 - root with len 0
41 int suff; // max suffix palindrome
42 long long ans;
43
44 bool addLetter(int pos) {
45 int cur = suff, curlen = 0;
46 int let = s[pos] - 'a';
47
48 while (true) {
49 curlen = tree[cur].len;
50 if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
51 break;
52 cur = tree[cur].sufflink;
53 }
54 if (tree[cur].next[let]) {
55 suff = tree[cur].next[let];
56 return false;
57 }
58
59 num++;
60 suff = num;
61 tree[num].len = tree[cur].len + 2;
62 tree[cur].next[let] = num;
63
64 if (tree[num].len == 1) {
65 tree[num].sufflink = 2;
66 tree[num].num = 1;
67 return true;
68 }
69
70 while (true) {
71 cur = tree[cur].sufflink;
72 curlen = tree[cur].len;
73 if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
74 tree[num].sufflink = tree[cur].next[let];
75 break;
76 }
77 }
78
79 tree[num].num = 1 + tree[tree[num].sufflink].num;
80
81 return true;
82 }
83
84 void initTree() {
85 num = 2; suff = 2;
86 tree[1].len = -1; tree[1].sufflink = 1;
87 tree[2].len = 0; tree[2].sufflink = 1;
88 }
89
90 int main() {
91 //assert(freopen("[Link]", "r", stdin));
92 //assert(freopen("[Link]", "w", stdout));
93
94 gets(s);
95 len = strlen(s);
96
97 initTree();
98
99 for (int i = 0; i < len; i++) {
100 addLetter(i);
101 ans += tree[suff].num;
102 }
103
104 cout << ans << endl;
105
106 return 0;
107 }

© 2016 GitHub, Inc. Terms Privacy Security Status Help Contact GitHub API Training Shop Blog About

You might also like