Note Book

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Strange Substring
Source            : CS Academy
Category          : String, Data Structure
Algorithm         : Suffix Tree
Verdict           : Accepted

You are given two strings  $A$  and  $B$ , consisting only of lowercase letters from the English alphabet. Count the number of distinct strings  $S$ , which are substrings of  $A$ , but not substrings of  $B$ .

#pragma once
#undef _GLIBCXX_DEBUG
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/rope"
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
void trace(int x) { cerr << x; }
void trace(long x) { cerr << x; }
void trace(long long x) { cerr << x; }
void trace(unsigned x) { cerr << x; }
void trace(unsigned long x) { cerr << x; }
void trace(unsigned long long x) { cerr << x; }
void trace(float x) { cerr << x; }
void trace(double x) { cerr << x; }
void trace(long double x) { cerr << x; }
void trace(char x) { cerr << '\'' << x << '\''; }
void trace(const char *x) { cerr << '\"' << x << '\"'; }
void trace(const string &x) { cerr << '\"' << x << '\"'; }
void trace(bool x) { cerr << (x ? "true" : "false"); }
template <typename A, typename B> void trace(const pair <A, B> &x) { cerr << '{'; trace(x.first); cerr << ','; trace(x.second); cerr << '}'; }
template <typename A, typename B, typename C> void trace(const tuple <A, B, C> &x) { cerr << '{'; trace(get <0> (x)); cerr << ','; trace(get <1> (x)); cerr << ','; trace(get <2> (x)); cerr << '}'; }
template <typename A, typename B, typename C, typename D> void trace(const tuple <A, B, C, D> &x) { cerr << '{'; trace(get <0> (x)); cerr << ','; trace(get <1> (x)); cerr << ','; trace(get <2> (x)); cerr << ','; trace(get <3> (x)); cerr << '}'; }
template <typename T> void trace(const T &x) { int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), trace(i); cerr << "}"; }
template <size_t N> void trace(bitset <N> v) { cerr << '{'; for (size_t i = 0; i < N; i++) cerr << static_cast <char> ('0' + v[i]); cerr << '}'; }
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) { trace(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif // ONLINE_JUDGE
template <typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T1, typename T2> using ordered_map = tree <T1, T2, less <T1>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> T binaryExpo(T a, T p) { if (p == 0) { return 1LL; } if (p == 1) { return a; } if (p & 1) { return a * binaryExpo(a, p - 1); } T ret = binaryExpo(a, p / 2); return ret * ret; }
template <typename T> T bigMod(T a, T p, T m) { if (p == 0) { return 1LL % m; } if (p == 1) { return a % m; } if (p & 1) { return (a % m * bigMod(a, p - 1, m)) % m; } T ret = bigMod(a, p / 2, m) % m; return (ret * ret) % m; }
template <typename T> T modInv(T a, T m) { return bigMod(a, m - 2, m); }
template <class T> bool MIN(T &a, T b) { return a > b ? (a = b, true) : false; }
template <class T> bool MAX(T &a, T b) { return a < b ? (a = b, true) : false; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define endl '\n'
#define pii pair <int, int>
#define pll pair <ll, ll>
#define mk make_pair
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define eb emplace_back
#define pb push_back
#define pf push_front
#define allUpper(a) transform(all(a), a.begin(), :: toupper)
#define allLower(a) transform(all(a), a.begin(), :: tolower)
#define LINE cerr << __LINE__ << " ";
#define memo(a, b) memset(a, b, sizeof a)
#define sz(a) (int)(a.size())
#define ook order_of_key // The number of items in a set that are strictly smaller than k
#define fbo find_by_order // It returns an iterator to the i'th largest element
#define ATCODER if (fopen("in.txt", "r")) { freopen("in.txt", "r", stdin); }
#define int long long int
const int maxn = 2e5 + 5;
const int logn = 19;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
/*
Algorithm : Suffix Tree
Tutorial : https://cp-algorithms.com/string/suffix-tree-ukkonen.html
https://www.geeksforgeeks.org/ukkonens-suffix-tree-construction-part-1/?ref=lbp
https://codeforces.com/blog/entry/16780
Visualization : https://brenden.github.io/ukkonen-animation/
Structure Details :
Root = 0
l = starting index of the substring
r = ending index of the substring + 1
Problem : https://codeforces.com/contest/427/problem/D
Statement : Given two strings s1 and s2 consist of lowercase Latin letters, find the smallest (by length)
common substring p of both s1 and s2, where p is a unique substring in s1 and also in s2.
*/
struct SuffixTree {
struct Node {
int l;
int r;
int par;
int link;
map <char, int> child;
Node(int l = 0, int r = 0, int par = -1)
: l(l), r(r), par(par), link(-1) {
child.clear();
}
void clean() {
l = 0;
r = 0;
par = -1;
link = -1;
child.clear();
}
int len() {
return r - l;
}
int &get(char c) {
if (child.count(c) == 0) {
child[c] = -1;
}
return child[c];
}
};
struct State {
int v;
int pos;
State() {}
State(int v, int pos)
: v(v), pos(pos) {}
};
string s;
int n;
int SZ;
vector <Node> stree;
State ptr;
SuffixTree() {}
void init(string &str) {
s = str;
n = str.size();
stree.clear(); stree.resize(4 * n + 5);
}
State go(State st, int l, int r) {
while (l < r) {
if (st.pos == stree[st.v].len()) {
st = State(stree[st.v].get(s[l]), 0);
if (st.v == -1) {
return st;
}
}
else {
assert(stree[st.v].l + st.pos >= 0);
if (s[ stree[st.v].l + st.pos ] != s[l]) {
return State(-1, -1);
}
if (r - l < stree[st.v].len() - st.pos) {
return State(st.v, st.pos + r - l);
}
l += stree[st.v].len() - st.pos;
st.pos = stree[st.v].len();
}
}
return st;
}
int split(State st) {
if (st.pos == stree[st.v].len()) {
return st.v;
}
if (st.pos == 0) {
return stree[st.v].par;
}
Node v = stree[st.v];
int id = SZ++;
stree[id] = Node(v.l, v.l + st.pos, v.par);
stree[v.par].get(s[v.l]) = id;
stree[id].get(s[v.l + st.pos]) = st.v;
assert(st.v >= 0);
stree[st.v].par = id;
stree[st.v].l += st.pos;
return id;
}
int get_link(int v) {
if (stree[v].link != -1) {
return stree[v].link;
}
if (stree[v].par == -1) {
return 0;
}
int to = get_link(stree[v].par);
return stree[v].link = split(go(State(to, stree[to].len()), stree[v].l + (stree[v].par == 0), stree[v].r));
}
void tree_extend(int pos) {
for(;;) {
State nptr = go(ptr, pos, pos + 1);
if (nptr.v != -1) {
ptr = nptr;
return;
}
int mid = split(ptr);
int leaf = SZ++;
stree[leaf] = Node(pos, n, mid);
stree[mid].get(s[pos]) = leaf;
ptr.v = get_link(mid);
ptr.pos = stree[ptr.v].len();
if (!mid) {
break;
}
}
}
void build_tree() {
SZ = 1;
ptr = {0, 0};
for (int i = 0; i < stree.size(); i++) {
stree[i].clean();
}
for (int i = 0; i < n; i++) {
tree_extend(i);
}
}
};
string s;
string t;
SuffixTree st;
int dfs(int u = 0) {
int sum = 0;
for (auto it : st.stree[u].child) {
char ch = it.ff;
int v = it.ss;
int l = st.stree[v].l;
int r = st.stree[v].r - 1;
debug(u, v, l, r);
if (l > sz(t)) {
sum += st.stree[v].len();
}
sum += dfs(v);
}
return sum;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cout.precision(12);
bool FILEIO = 1;
if (FILEIO and fopen("in.txt", "r")) {
freopen("in.txt", "r", stdin);
}
cin >> s >> t;
string str = t + "#" + s;
st.init(str);
st.build_tree();
int ans = dfs();
cout << ans << endl;
}

Note Book

Tuesday, August 25, 2020

No comments:

Post a Comment