Resources:
adilet.org-palindromic-tree
Rezwan's CP Blog
Cf blog1
Cf-blog02
geeksForGeeks
Eertree (or palindromic tree)
Problems:
LPS
E. Palindromes in a Tree
TREEPAL
the-story-of-stringland
NUMOFPAL
The Number of Palindromes
Implementation:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ///http://acm.hdu.edu.cn/showproblem.php?pid=3948 | |
| #include <bits/stdc++.h> | |
| #include <queue> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 100005 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| #define dbg1(x) cerr << #x << " = " << x << endl; | |
| #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| template < typename F, typename S > | |
| ostream& operator << ( ostream& os, const pair< F, S > & p ) { | |
| return os << "(" << p.first << ", " << p.second << ")"; | |
| } | |
| template < typename T > | |
| ostream &operator << ( ostream & os, const vector< T > &v ) { | |
| os << "{"; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin() ) os << ", "; | |
| os << *it; | |
| } | |
| return os << "}"; | |
| } | |
| template < typename T > | |
| ostream &operator << ( ostream & os, const set< T > &v ) { | |
| os << "["; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin()) os << ", "; | |
| os << *it; | |
| } | |
| return os << "]"; | |
| } | |
| template < typename F, typename S > | |
| ostream &operator << ( ostream & os, const map< F, S > &v ) { | |
| os << "["; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin() ) os << ", "; | |
| os << it -> first << " = " << it -> second ; | |
| } | |
| return os << "]"; | |
| } | |
| #define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0) | |
| clock_t tStart = clock(); | |
| #define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC) | |
| void faltu () { cerr << endl; } | |
| template <typename T> | |
| void faltu( T a[], int n ) { | |
| for (int i = 0; i < n; ++i) cerr << a[i] << ' '; | |
| cerr << endl; | |
| } | |
| template <typename T, typename ... hello> | |
| void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); } | |
| // Program showing a policy-based data structure. | |
| #include <ext/pb_ds/assoc_container.hpp> // Common file | |
| #include <ext/pb_ds/tree_policy.hpp> | |
| #include <functional> // for less | |
| #include <iostream> | |
| using namespace __gnu_pbds; | |
| using namespace std; | |
| // GNU link : https://goo.gl/WVDL6g | |
| typedef tree<int, null_type, less_equal<int>, rb_tree_tag, | |
| tree_order_statistics_node_update> | |
| new_data_set; | |
| /**___________________________________________________**/ | |
| const int N = 105000; | |
| struct node | |
| { | |
| int next[32]; | |
| int len; | |
| int suffixLink; | |
| int num; | |
| }; | |
| int len; | |
| char s[N]; | |
| //string s; | |
| node Tree[N]; | |
| 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; | |
| int curlen = 0; | |
| int let = s[pos] - 'a'; | |
| while (true) | |
| { | |
| curlen = Tree[cur].len; | |
| if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) | |
| break; | |
| cur = Tree[cur].suffixLink; | |
| } | |
| 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].suffixLink = 2; | |
| Tree[num].num = 1; | |
| return true; | |
| } | |
| while (true) { | |
| cur = Tree[cur].suffixLink; | |
| curlen = Tree[cur].len; | |
| if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) { | |
| Tree[num].suffixLink = Tree[cur].next[let]; | |
| break; | |
| } | |
| } | |
| Tree[num].num = 1 + Tree[Tree[num].suffixLink].num; | |
| return true; | |
| } | |
| void initTree() | |
| { | |
| memset(Tree, 0, sizeof Tree); | |
| num = 2; | |
| suff = 2; | |
| Tree[1].len = -1; | |
| Tree[1].suffixLink = 1; | |
| Tree[2].len = 0; | |
| Tree[2].suffixLink = 1; | |
| } | |
| int main() | |
| { | |
| //FASTIO | |
| ///* | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| int t; | |
| cin >> t; | |
| int cs = 0; | |
| while (t--) { | |
| ans = 0; | |
| cin >> s; | |
| len = strlen(s); | |
| initTree(); | |
| for (int i = 0; i < len; i++) { | |
| ans += addletter(i); | |
| //ans += Tree[suff].num; | |
| } | |
| cout << "Case #" << ++cs << ": " << ans << endl; | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ///https://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=1750#1 | |
| //https://www.spoj.com/problems/NUMOFPAL/ | |
| #include <bits/stdc++.h> | |
| #include <queue> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 100005 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| #define dbg1(x) cerr << #x << " = " << x << endl; | |
| #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| template < typename F, typename S > | |
| ostream& operator << ( ostream& os, const pair< F, S > & p ) { | |
| return os << "(" << p.first << ", " << p.second << ")"; | |
| } | |
| template < typename T > | |
| ostream &operator << ( ostream & os, const vector< T > &v ) { | |
| os << "{"; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin() ) os << ", "; | |
| os << *it; | |
| } | |
| return os << "}"; | |
| } | |
| template < typename T > | |
| ostream &operator << ( ostream & os, const set< T > &v ) { | |
| os << "["; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin()) os << ", "; | |
| os << *it; | |
| } | |
| return os << "]"; | |
| } | |
| template < typename F, typename S > | |
| ostream &operator << ( ostream & os, const map< F, S > &v ) { | |
| os << "["; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin() ) os << ", "; | |
| os << it -> first << " = " << it -> second ; | |
| } | |
| return os << "]"; | |
| } | |
| #define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0) | |
| clock_t tStart = clock(); | |
| #define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC) | |
| void faltu () { cerr << endl; } | |
| template <typename T> | |
| void faltu( T a[], int n ) { | |
| for (int i = 0; i < n; ++i) cerr << a[i] << ' '; | |
| cerr << endl; | |
| } | |
| template <typename T, typename ... hello> | |
| void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); } | |
| // Program showing a policy-based data structure. | |
| #include <ext/pb_ds/assoc_container.hpp> // Common file | |
| #include <ext/pb_ds/tree_policy.hpp> | |
| #include <functional> // for less | |
| #include <iostream> | |
| using namespace __gnu_pbds; | |
| using namespace std; | |
| // GNU link : https://goo.gl/WVDL6g | |
| typedef tree<int, null_type, less_equal<int>, rb_tree_tag, | |
| tree_order_statistics_node_update> | |
| new_data_set; | |
| /**___________________________________________________**/ | |
| const int N = 105000; | |
| struct node | |
| { | |
| int next[32]; | |
| int len; | |
| int suffixLink; | |
| int num; | |
| }; | |
| int len; | |
| //char s[N]; | |
| string s; | |
| node Tree[N]; | |
| 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; | |
| int curlen = 0; | |
| int let = s[pos] - 'a'; | |
| while (true) | |
| { | |
| curlen = Tree[cur].len; | |
| if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) | |
| break; | |
| cur = Tree[cur].suffixLink; | |
| } | |
| 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].suffixLink = 2; | |
| Tree[num].num = 1; | |
| return true; | |
| } | |
| while (true) { | |
| cur = Tree[cur].suffixLink; | |
| curlen = Tree[cur].len; | |
| if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) { | |
| Tree[num].suffixLink = Tree[cur].next[let]; | |
| break; | |
| } | |
| } | |
| Tree[num].num = 1 + Tree[Tree[num].suffixLink].num; | |
| return true; | |
| } | |
| void initTree() | |
| { | |
| memset(Tree, 0, sizeof Tree); | |
| num = 2; | |
| suff = 2; | |
| Tree[1].len = -1; | |
| Tree[1].suffixLink = 1; | |
| Tree[2].len = 0; | |
| Tree[2].suffixLink = 1; | |
| } | |
| int main() | |
| { | |
| //FASTIO | |
| ///* | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| ans = 0; | |
| getline(cin, s); | |
| len = s.length(); | |
| initTree(); | |
| for (int i = 0; i < len; i++) { | |
| addletter(i); | |
| ans += Tree[suff].num; | |
| } | |
| cout << ans << endl; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 100005 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| #define dbg1(x) cerr << #x << " = " << x << endl; | |
| #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| template < typename F, typename S > | |
| ostream& operator << ( ostream& os, const pair< F, S > & p ) { | |
| return os << "(" << p.first << ", " << p.second << ")"; | |
| } | |
| template < typename T > | |
| ostream &operator << ( ostream & os, const vector< T > &v ) { | |
| os << "{"; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin() ) os << ", "; | |
| os << *it; | |
| } | |
| return os << "}"; | |
| } | |
| template < typename T > | |
| ostream &operator << ( ostream & os, const set< T > &v ) { | |
| os << "["; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin()) os << ", "; | |
| os << *it; | |
| } | |
| return os << "]"; | |
| } | |
| template < typename F, typename S > | |
| ostream &operator << ( ostream & os, const map< F, S > &v ) { | |
| os << "["; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin() ) os << ", "; | |
| os << it -> first << " = " << it -> second ; | |
| } | |
| return os << "]"; | |
| } | |
| #define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0) | |
| clock_t tStart = clock(); | |
| #define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC) | |
| void faltu () { cerr << endl; } | |
| template <typename T> | |
| void faltu( T a[], int n ) { | |
| for (int i = 0; i < n; ++i) cerr << a[i] << ' '; | |
| cerr << endl; | |
| } | |
| template <typename T, typename ... hello> | |
| void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); } | |
| // Program showing a policy-based data structure. | |
| #include <ext/pb_ds/assoc_container.hpp> // Common file | |
| #include <ext/pb_ds/tree_policy.hpp> | |
| #include <functional> // for less | |
| #include <iostream> | |
| using namespace __gnu_pbds; | |
| using namespace std; | |
| // GNU link : https://goo.gl/WVDL6g | |
| typedef tree<int, null_type, less_equal<int>, rb_tree_tag, | |
| tree_order_statistics_node_update> | |
| new_data_set; | |
| /**___________________________________________________**/ | |
| const int N = 100005; | |
| int idx, t; | |
| int link[N]; | |
| int len[N]; | |
| int tr[N][26]; | |
| string s; | |
| void initTree() | |
| { | |
| memset(tr, 0, sizeof tr); | |
| memset(link, 0, sizeof link); | |
| memset(len, 0, sizeof len); | |
| len[1] = -1; | |
| link[1] = 1; | |
| len[2] = 0; | |
| link[2] = 1; | |
| idx = 2; | |
| t = 2; | |
| } | |
| void addletter(int pos) | |
| { | |
| while (s[pos - len[t] - 1] != s[pos]) t = link[t]; | |
| int x = link[t]; | |
| while (s[pos - len[x] - 1] != s[pos]) x = link[x]; | |
| int c = s[pos] - 'a'; | |
| if (!tr[t][c]) { | |
| tr[t][c] = ++idx; | |
| len[idx] = len[t] + 2; | |
| link[idx] = len[idx] == 1 ? 2 : tr[x][c]; | |
| } | |
| t = tr[t][c]; | |
| } | |
| int main() | |
| { | |
| //FASTIO | |
| ///* | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| int T; | |
| scanf("%d", &T); | |
| //T = 1; | |
| for (int cs = 1; cs <= T; cs++) { | |
| initTree(); | |
| cin >> s; | |
| s = ' ' + s; | |
| int n = s.size(); | |
| for (int i = 1; i < n; i++) { | |
| addletter(i); | |
| } | |
| printf("Case #%d: %d\n", cs, idx - 2); | |
| } | |
| return 0; | |
| } |
No comments:
Post a Comment