Stupid
1 removal
182 lines
1 addition
182 lines
#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
using namespace std;
#include "spoj.h"
#include "spoj.h"
const int N = 1e5 + 9;
const int N = 1e5 + 9;
/*
/*
-> diff(v) = len(v) - len(link(v))
-> diff(v) = len(v) - len(link(v))
-> series link will lead from the vertex v to the vertex u corresponding
-> series link will lead from the vertex v to the vertex u corresponding
to the maximum suffix palindrome of v which satisfies diff(v) != diff(u)
to the maximum suffix palindrome of v which satisfies diff(v) != diff(u)
-> path within series links to the root contains only O(log n) vertices
-> path within series links to the root contains only O(log n) vertices
-> cnt contains the number of palindromic suffixes of the node
-> cnt contains the number of palindromic suffixes of the node
*/
*/
struct PalindromicTree {
struct PalindromicTree {
struct node {
struct node {
int nxt[26], len, st, en, link, diff, slink, cnt, oc;
int nxt[26], len, st, en, link, diff, slink, cnt, oc;
};
};
string s; vector<node> t;
string s; vector<node> t;
int sz, last;
int sz, last;
PalindromicTree() {}
PalindromicTree() {}
PalindromicTree(string _s) {
PalindromicTree(string _s) {
s = _s; int n = s.size();
s = _s; int n = s.size();
t.clear(); t.resize(n + 9);
t.clear(); t.resize(n + 9);
sz = 2, last = 2;
sz = 2, last = 2;
t[1].len = -1, t[1].link = 1;
t[1].len = -1, t[1].link = 1;
t[2].len = 0, t[2].link = 1;
t[2].len = 0, t[2].link = 1;
t[1].diff = t[2].diff = 0;
t[1].diff = t[2].diff = 0;
t[1].slink = 1; t[2].slink = 2;
t[1].slink = 1; t[2].slink = 2;
}
}
int extend(int pos) { // returns 1 if it creates a new palindrome
int extend(int pos) { // returns 1 if it creates a new palindrome
int cur = last, curlen = 0;
int cur = last, curlen = 0;
int ch = s[pos] - 'a';
int ch = s[pos] - 'a';
while (1) {
while (1) {
curlen = t[cur].len;
curlen = t[cur].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break;
cur = t[cur].link;
cur = t[cur].link;
}
}
if (t[cur].nxt[ch]) {
if (t[cur].nxt[ch]) {
last = t[cur].nxt[ch];
last = t[cur].nxt[ch];
t[last].oc++;
t[last].oc++;
return 0;
return 0;
}
}
sz++; last = sz;
sz++; last = sz;
t[sz].oc = 1; t[sz].len = t[cur].len + 2;
t[sz].oc = 1; t[sz].len = t[cur].len + 2;
t[cur].nxt[ch] = sz;
t[cur].nxt[ch] = sz;
t[sz].en = pos; t[sz].st = pos - t[sz].len + 1;
t[sz].en = pos; t[sz].st = pos - t[sz].len + 1;
if (t[sz].len == 1) {
if (t[sz].len == 1) {
t[sz].link = 2; t[sz].cnt = 1;
t[sz].link = 2; t[sz].cnt = 1;
t[sz].diff = 1; t[sz].slink = 2;
t[sz].diff = 1; t[sz].slink = 2;
return 1;
return 1;
}
}
while (1) {
while (1) {
cur = t[cur].link; curlen = t[cur].len;
cur = t[cur].link; curlen = t[cur].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
t[sz].link = t[cur].nxt[ch];
t[sz].link = t[cur].nxt[ch];
break;
break;
}
}
}
}
t[sz].cnt = 1 + t[t[sz].link].cnt;
t[sz].cnt = 1 + t[t[sz].link].cnt;
t[sz].diff = t[sz].len - t[t[sz].link].len;
t[sz].diff = t[sz].len - t[t[sz].link].len;
if (t[sz].diff == t[t[sz].link].diff) t[sz].slink = t[t[sz].link].slink;
if (t[sz].diff == t[t[sz].link].diff) t[sz].slink = t[t[sz].link].slink;
else t[sz].slink = t[sz].link;
else t[sz].slink = t[sz].link;
return 1;
return 1;
}
}
void calc_occurrences() {
void calc_occurrences() {
for (int i = sz; i >= 3; i--) t[t[i].link].oc += t[i].oc;
for (int i = sz; i >= 3; i--) t[t[i].link].oc += t[i].oc;
}
}
};
};
// len -> largest string length of the corresponding endpos-equivalent class
// len -> largest string length of the corresponding endpos-equivalent class
// link -> longest suffix that is another endpos-equivalent class.
// link -> longest suffix that is another endpos-equivalent class.
// firstpos -> 1 indexed end position of the first occurrence of the largest string of that node
// firstpos -> 1 indexed end position of the first occurrence of the largest string of that node
// minlen(v) -> smallest string of node v = len(link(v)) + 1
// minlen(v) -> smallest string of node v = len(link(v)) + 1
// terminal nodes -> store the suffixes
// terminal nodes -> store the suffixes
struct SuffixAutomaton {
struct SuffixAutomaton {
struct node {
struct node {
int len, link, firstpos;
int len, link, firstpos;
map<char, int> nxt;
map<char, int> nxt;
};
};
int sz, last;
int sz, last;
vector<node> t;
vector<node> t;
vector<int> terminal;
vector<int> terminal;
vector<int> dp;
vector<int> dp;
vector<vector<int>> g;
vector<vector<int>> g;
SuffixAutomaton() {}
SuffixAutomaton() {}
SuffixAutomaton(int n) {
SuffixAutomaton(int n) {
t.resize(2 * n); terminal.resize(2 * n, 0);
t.resize(2 * n); terminal.resize(2 * n, 0);
dp.resize(2 * n, -1); sz = 1; last = 0;
dp.resize(2 * n, -1); sz = 1; last = 0;
g.resize(2 * n);
g.resize(2 * n);
t[0].len = 0; t[0].link = -1; t[0].firstpos = 0;
t[0].len = 0; t[0].link = -1; t[0].firstpos = 0;
}
}
void extend(char c) {
void extend(char c) {
int p = last;
int p = last;
if (t[p].nxt.count(c)) {
if (t[p].nxt.count(c)) {
int q = t[p].nxt[c];
int q = t[p].nxt[c];
if (t[q].len == t[p].len + 1) {
if (t[q].len == t[p].len + 1) {
last = q;
last = q;
return;
return;
}
}
int clone = sz++;
int clone = sz++;
t[clone] = t[q];
t[clone] = t[q];
t[clone].len = t[p].len + 1;
t[clone].len = t[p].len + 1;
t[q].link = clone;
t[q].link = clone;
last = clone;
last = clone;
while (p != -1 && t[p].nxt[c] == q) {
while (p != -1 && t[p].nxt[c] == q) {
t[p].nxt[c] = clone;
t[p].nxt[c] = clone;
p = t[p].link;
p = t[p].link;
}
}
return;
return;
}
}
int cur = sz++;
int cur = sz++;
t[cur].len = t[last].len + 1;
t[cur].len = t[last].len + 1;
t[cur].firstpos = t[cur].len;
t[cur].firstpos = t[cur].len;
p = last;
p = last;
while (p != -1 && !t[p].nxt.count(c)) {
while (p != -1 && !t[p].nxt.count(c)) {
t[p].nxt[c] = cur;
t[p].nxt[c] = cur;
p = t[p].link;
p = t[p].link;
}
}
if (p == -1) t[cur].link = 0;
if (p == -1) t[cur].link = 0;
else {
else {
int q = t[p].nxt[c];
int q = t[p].nxt[c];
if (t[p].len + 1 == t[q].len) t[cur].link = q;
if (t[p].len + 1 == t[q].len) t[cur].link = q;
else {
else {
int clone = sz++;
int clone = sz++;
t[clone] = t[q];
t[clone] = t[q];
t[clone].len = t[p].len + 1;
t[clone].len = t[p].len + 1;
while (p != -1 && t[p].nxt[c] == q) {
while (p != -1 && t[p].nxt[c] == q) {
t[p].nxt[c] = clone;
t[p].nxt[c] = clone;
p = t[p].link;
p = t[p].link;
}
}
t[q].link = t[cur].link = clone;
t[q].link = t[cur].link = clone;
}
}
}
}
last = cur;
last = cur;
}
}
void build(string &s) {
void build(string &s) {
for (auto x: s) {
for (auto x: s) {
extend(x);
extend(x);
terminal[last] = 1;
terminal[last] = 1;
}
}
}
}
};
};
long long distinct(string s) {
long long distinct(string s) {
SuffixAutomaton sa(s.size());
SuffixAutomaton sa(s.size());
sa.build(s);
sa.build(s);
long long ans = 0;
long long ans = 0;
for (int i = 1; i < sa.sz; i++) ans += sa.t[i].len - sa.t[sa.t[i].link].len;
for (int i = 1; i < sa.sz; i++) ans += sa.t[i].len - sa.t[sa.t[i].link].len;
return ans;
return ans;
}
}
long long palindromic(string s) {
long long palindromic(string s) {
PalindromicTree t(s);
PalindromicTree t(s);
for (int i = 0; i < s.size(); i++) t.extend(i);
for (int i = 0; i < s.size(); i++) t.extend(i);
t.calc_occurrences();
t.calc_occurrences();
long long ans = 0;
long long ans = 0;
for (int i = 3; i <= t.sz; i++) ans += t.t[i].cnt;
for (int i = 3; i <= t.sz; i++) ans += t.t[i].oc;
return ans;
return ans;
}
}
char s[N];
char s[N];
int main(){
int main(){
int t, n;
int t, n;
spoj_init();
spoj_init();
fscanf(spoj_p_in, "%d", &t);
fscanf(spoj_p_in, "%d", &t);
for (int tt = 1; tt <= t; tt++) {
for (int tt = 1; tt <= t; tt++) {
fscanf(spoj_p_in, "%d", &n);
fscanf(spoj_p_in, "%d", &n);
int z;
int z;
spoj_assert(fscanf(spoj_t_out, "%d", &z) == 1);
spoj_assert(fscanf(spoj_t_out, "%d", &z) == 1);
spoj_assert(1 <= z && z <= 7 * n);
spoj_assert(1 <= z && z <= 7 * n);
spoj_assert(fscanf(spoj_t_out, "%s", s) == 1);
spoj_assert(fscanf(spoj_t_out, "%s", s) == 1);
string p = string(s);
string p = string(s);
int sz = p.size();
int sz = p.size();
spoj_assert(z == sz);
spoj_assert(z == sz);
for (char c: p) spoj_assert('a' <= c && c <= 'z');
for (char c: p) spoj_assert('a' <= c && c <= 'z');
long long tot = distinct(p) - palindromic(p);
long long tot = distinct(p) - palindromic(p);
spoj_assert(tot == n);
spoj_assert(tot == n);
}
}
char extra[100];
char extra[100];
spoj_assert(fscanf(spoj_t_out, "%s", extra) != 1);
spoj_assert(fscanf(spoj_t_out, "%s", extra) != 1);
return 0;
return 0;
}
}