Compare text

Find the difference between two text files

Real-time diff

Unified diff

Collapse lines

Highlight change

Syntax highlighting

Tools

Stupid

Created 4 years agoDiff never expires

1 removal

182 lines

1 addition

182 lines

#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;

}

Saved diffs

Original text

Open file

#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;
}

Changed text

Open file

#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].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;
}