Comparar texto

Encuentra la diferencia entre dos archivos de texto

Editor live

Ocultar espacios en blanco

Ocultar sin cambios

Sin ajuste de línea

Vista

Nivel de detalle

Estilos de texto

Resaltado de sintaxis

Diffchecker Desktop La forma más segura de usar Diffchecker. ¡Obtén la app de Diffchecker Desktop: tus diffs nunca salen de tu computadora!Obtener Desktop

Stupid

Creado hace 6 añosEl diff nunca expira

1 eliminación

Líneas
Total
Eliminado

Caracteres
Total
Eliminado

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

182 líneas

1 adición

Líneas
Total
Añadido

Caracteres
Total
Añadido

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

182 líneas

#include<bits/stdc++.h>

using namespace std;

#include "spoj.h"

const int N = 1e5 + 9;

-> diff(v) = len(v) - len(link(v))

-> 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)

-> path within series links to the root contains only O(log n) vertices

-> cnt contains the number of palindromic suffixes of the node

struct PalindromicTree {

struct node {

int nxt[26], len, st, en, link, diff, slink, cnt, oc;

};

string s; vector<node> t;

int sz, last;

PalindromicTree() {}

PalindromicTree(string _s) {

s = _s; int n = s.size();

t.clear(); t.resize(n + 9);

sz = 2, last = 2;

t[1].len = -1, t[1].link = 1;

t[2].len = 0, t[2].link = 1;

t[1].diff = t[2].diff = 0;

t[1].slink = 1; t[2].slink = 2;

}

int extend(int pos) { // returns 1 if it creates a new palindrome

int cur = last, curlen = 0;

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

while (1) {

curlen = t[cur].len;

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

cur = t[cur].link;

}

if (t[cur].nxt[ch]) {

last = t[cur].nxt[ch];

t[last].oc++;

return 0;

}

sz++; last = sz;

t[sz].oc = 1; t[sz].len = t[cur].len + 2;

t[cur].nxt[ch] = sz;

t[sz].en = pos; t[sz].st = pos - t[sz].len + 1;

if (t[sz].len == 1) {

t[sz].link = 2; t[sz].cnt = 1;

t[sz].diff = 1; t[sz].slink = 2;

return 1;

}

while (1) {

cur = t[cur].link; curlen = t[cur].len;

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

t[sz].link = t[cur].nxt[ch];

break;

}

t[sz].cnt = 1 + t[t[sz].link].cnt;

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;

else t[sz].slink = t[sz].link;

return 1;

}

void calc_occurrences() {

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

// 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

// minlen(v) -> smallest string of node v = len(link(v)) + 1

// terminal nodes -> store the suffixes

struct SuffixAutomaton {

struct node {

int len, link, firstpos;

map<char, int> nxt;

};

int sz, last;

vector<node> t;

vector<int> terminal;

vector<int> dp;

vector<vector<int>> g;

SuffixAutomaton() {}

SuffixAutomaton(int n) {

t.resize(2 * n); terminal.resize(2 * n, 0);

dp.resize(2 * n, -1); sz = 1; last = 0;

g.resize(2 * n);

t[0].len = 0; t[0].link = -1; t[0].firstpos = 0;

}

void extend(char c) {

int p = last;

if (t[p].nxt.count(c)) {

int q = t[p].nxt[c];

if (t[q].len == t[p].len + 1) {

last = q;

return;

}

int clone = sz++;

t[clone] = t[q];

t[clone].len = t[p].len + 1;

t[q].link = clone;

last = clone;

while (p != -1 && t[p].nxt[c] == q) {

t[p].nxt[c] = clone;

p = t[p].link;

}

return;

}

int cur = sz++;

t[cur].len = t[last].len + 1;

t[cur].firstpos = t[cur].len;

p = last;

while (p != -1 && !t[p].nxt.count(c)) {

t[p].nxt[c] = cur;

p = t[p].link;

}

if (p == -1) t[cur].link = 0;

else {

int q = t[p].nxt[c];

if (t[p].len + 1 == t[q].len) t[cur].link = q;

else {

int clone = sz++;

t[clone] = t[q];

t[clone].len = t[p].len + 1;

while (p != -1 && t[p].nxt[c] == q) {

t[p].nxt[c] = clone;

p = t[p].link;

}

t[q].link = t[cur].link = clone;

}

last = cur;

}

void build(string &s) {

for (auto x: s) {

extend(x);

terminal[last] = 1;

}

};

long long distinct(string s) {

SuffixAutomaton sa(s.size());

sa.build(s);

long long ans = 0;

for (int i = 1; i < sa.sz; i++) ans += sa.t[i].len - sa.t[sa.t[i].link].len;

return ans;

}

long long palindromic(string s) {

PalindromicTree t(s);

for (int i = 0; i < s.size(); i++) t.extend(i);

t.calc_occurrences();

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;

}

char s[N];

int main(){

int t, n;

spoj_init();

fscanf(spoj_p_in, "%d", &t);

for (int tt = 1; tt <= t; tt++) {

fscanf(spoj_p_in, "%d", &n);

int z;

spoj_assert(fscanf(spoj_t_out, "%d", &z) == 1);

spoj_assert(1 <= z && z <= 7 * n);

spoj_assert(fscanf(spoj_t_out, "%s", s) == 1);

string p = string(s);

int sz = p.size();

spoj_assert(z == sz);

for (char c: p) spoj_assert('a' <= c && c <= 'z');

long long tot = distinct(p) - palindromic(p);

spoj_assert(tot == n);

}

char extra[100];

spoj_assert(fscanf(spoj_t_out, "%s", extra) != 1);

return 0;

}

Diferencias guardadas

Texto original

Abrir archivo

#include<bits/stdc++.h>
using namespace std;
#include "spoj.h"

const int N = 1e5 + 9;

/*
-> diff(v) = len(v) - len(link(v))
-> 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)
-> path within series links to the root contains only O(log n) vertices
-> cnt contains the number of palindromic suffixes of the node
*/
struct PalindromicTree {
    struct node {
        int nxt[26], len, st, en, link, diff, slink, cnt, oc;
    };
    string s; vector<node> t;
    int sz, last;
    PalindromicTree() {}
    PalindromicTree(string _s) {
        s = _s; int n = s.size();
        t.clear(); t.resize(n + 9);
        sz = 2, last = 2;
        t[1].len = -1, t[1].link = 1;
        t[2].len = 0, t[2].link = 1;
        t[1].diff = t[2].diff = 0;
        t[1].slink = 1; t[2].slink = 2;
    }
    int extend(int pos) { // returns 1 if it creates a new palindrome
        int cur = last, curlen = 0;
        int ch = s[pos] - 'a';
        while (1) {
            curlen = t[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break;
            cur = t[cur].link;
        }
        if (t[cur].nxt[ch]) {
            last = t[cur].nxt[ch];
            t[last].oc++;
            return 0;
        }
        sz++; last = sz;
        t[sz].oc = 1; t[sz].len = t[cur].len + 2;
        t[cur].nxt[ch] = sz;
        t[sz].en = pos; t[sz].st = pos - t[sz].len + 1;
        if (t[sz].len == 1) {
            t[sz].link = 2; t[sz].cnt = 1;
            t[sz].diff = 1; t[sz].slink = 2;
            return 1;
        }
        while (1) {
            cur = t[cur].link; curlen = t[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
                t[sz].link = t[cur].nxt[ch];
                break;
            }
        }
        t[sz].cnt = 1 + t[t[sz].link].cnt;
        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;
        else t[sz].slink = t[sz].link;
        return 1;
    }
    void calc_occurrences() {
        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
// 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
// minlen(v) -> smallest string of node v = len(link(v)) + 1
// terminal nodes -> store the suffixes
struct SuffixAutomaton {
    struct node {
        int len, link, firstpos;
        map<char, int> nxt;
    };
    int sz, last;
    vector<node> t;
    vector<int> terminal;
    vector<int> dp;
    vector<vector<int>> g;
    SuffixAutomaton() {}
    SuffixAutomaton(int n) {
        t.resize(2 * n); terminal.resize(2 * n, 0);
        dp.resize(2 * n, -1); sz = 1; last = 0;
        g.resize(2 * n);
        t[0].len = 0; t[0].link = -1; t[0].firstpos = 0;
    }
    void extend(char c) {
        int p = last;
        if (t[p].nxt.count(c)) {
            int q = t[p].nxt[c];
            if (t[q].len == t[p].len + 1) {
                last = q;
                return;
            }
            int clone = sz++;
            t[clone] = t[q];
            t[clone].len = t[p].len + 1;
            t[q].link = clone;
            last = clone;
            while (p != -1 && t[p].nxt[c] == q) {
                t[p].nxt[c] = clone;
                p = t[p].link;
            }
            return;
        }
        int cur = sz++;
        t[cur].len = t[last].len + 1;
        t[cur].firstpos = t[cur].len;
        p = last;
        while (p != -1 && !t[p].nxt.count(c)) {
            t[p].nxt[c] = cur;
            p = t[p].link;
        }
        if (p == -1) t[cur].link = 0;
        else {
            int q = t[p].nxt[c];
            if (t[p].len + 1 == t[q].len) t[cur].link = q;
            else {
                int clone = sz++;
                t[clone] = t[q];
                t[clone].len = t[p].len + 1;
                while (p != -1 && t[p].nxt[c] == q) {
                    t[p].nxt[c] = clone;
                    p = t[p].link;
                }
                t[q].link = t[cur].link = clone;
            }
        }
        last = cur;
    }
    void build(string &s) {
        for (auto x: s) {
            extend(x);
            terminal[last] = 1;
        }
    }
};
long long distinct(string s) {
    SuffixAutomaton sa(s.size());
    sa.build(s);
    long long ans = 0;
    for (int i = 1; i < sa.sz; i++) ans += sa.t[i].len - sa.t[sa.t[i].link].len;
    return ans;
}
long long palindromic(string s) {
    PalindromicTree t(s);
    for (int i = 0; i < s.size(); i++) t.extend(i);
    t.calc_occurrences();
    long long ans = 0;
    for (int i = 3; i <= t.sz; i++) ans += t.t[i].cnt;
    return ans;
}

char s[N];
int main(){
  int t, n;
  spoj_init();
  fscanf(spoj_p_in, "%d", &t);
  for (int tt = 1; tt <= t; tt++) {
    fscanf(spoj_p_in, "%d", &n);
    int z;
    spoj_assert(fscanf(spoj_t_out, "%d", &z) == 1);
    spoj_assert(1 <= z && z <= 7 * n);
    spoj_assert(fscanf(spoj_t_out, "%s", s) == 1);
    string p = string(s);
    int sz = p.size();
    spoj_assert(z == sz);
    for (char c: p) spoj_assert('a' <= c && c <= 'z');
    long long tot = distinct(p) - palindromic(p);
    spoj_assert(tot == n);
  }
  char extra[100];
  spoj_assert(fscanf(spoj_t_out, "%s", extra) != 1);
  return 0;
}

Texto modificado

Abrir archivo

#include<bits/stdc++.h>
using namespace std;
#include "spoj.h"

const int N = 1e5 + 9;