比較文本

尋找兩個文字檔案之間的差異

Real-time diff

Unified diff

Collapse lines

Highlight change

Syntax highlighting

工具

Diffchecker Desktop The most secure way to run Diffchecker. Get the Diffchecker Desktop app: your diffs never leave your computer!Get Desktop

Comparing sensitive data, confidential files or internal emails?

Most legal and privacy policies prohibit uploading sensitive data online. Diffchecker Desktop ensures your confidential information never leaves your computer. Work offline and compare documents securely.

Download Diffchecker Desktop Learn more

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;

}

已保存差異

原始文本

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

更改後文本

Open file

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

const int N = 1e5 + 9;