Author : Dipu Kumar Mohanto
CSE, Batch - 6
BRUR.
Problem Statement : Another Dirty String
Source : toph.co
Category : String, Data Structure
Algorithm : Suffix Automata, KMP, Segment Tree
Verdict : Accepted
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define vi vector <int>
#define eb emplace_back
#define sze(a) (int)a.size()
static const int maxn = 1e5 + 5;
string A, B, C;
int occ[maxn], cumocc[maxn];
inline vi longestPreffixSuffix(string pat)
{
vi lps;
lps.eb(0);
int i = 1, j = 0;
int len = sze(pat);
while (i < len)
{
if (pat[i] == pat[j])
{
i++;
j++;
lps.eb(j);
}
else
{
if (j)
{
j = lps[j-1];
}
else
{
i++;
lps.eb(0);
}
}
}
return lps;
}
inline void kmp(string text, string pat)
{
int lenText = sze(text);
int lenPat = sze(pat);
vi lps = longestPreffixSuffix(pat);
int i = 0, j = 0;
while (i < lenText)
{
if (text[i] == pat[j])
{
i++;
j++;
}
if (j == lenPat)
{
occ[i-1-lenPat+1] = 1;
j = lps[j-1];
}
else if (i < lenText && text[i] != pat[j])
{
if (j) j = lps[j-1];
else i++;
}
}
}
struct segmentTree
{
int lastocc;
void assignLeaf(int val, int pos)
{
lastocc = -1;
if (val == 1) lastocc = pos;
}
void marge(segmentTree l, segmentTree r)
{
if (l.lastocc > r.lastocc) lastocc = l.lastocc;
else if (l.lastocc < r.lastocc) lastocc = r.lastocc;
else lastocc = l.lastocc;
}
} tree[maxn << 2];
inline void build(int node, int a, int b)
{
if (a == b)
{
tree[node].assignLeaf(occ[a], a);
return;
}
int lft = node << 1;
int rgt = lft | 1;
int mid = (a + b) >> 1;
build(lft, a, mid);
build(rgt, mid+1, b);
tree[node].marge(tree[lft], tree[rgt]);
}
inline segmentTree query(int node, int a, int b, int i, int j)
{
if (a > b || a > j || b < i)
{
segmentTree nul;
nul.lastocc = -1;
return nul;
}
if (a >= i && b <= j) return tree[node];
int lft = node << 1;
int rgt = lft | 1;
int mid = (a + b) >> 1;
segmentTree p, q, res;
p = query(lft, a, mid, i, j);
q = query(rgt, mid+1, b, i, j);
res.marge(p, q);
return res;
}
struct state
{
int len, link;
map <char, int> next;
};
state st[maxn << 1];
int sz, last;
inline void init()
{
sz = last = 0;
st[0].len = 0;
st[0].link = -1;
st[0].next.clear();
++sz;
for (int i = 1; i < (maxn << 1); i++)
{
st[i].len = 0;
st[i].link = 0;
st[i].next.clear();
}
}
inline void sz_extend(char c)
{
int cur = sz++;
st[cur].len = st[last].len + 1;
int p;
for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link)
{
st[p].next[c] = cur;
}
if (p == -1)
{
st[cur].link = 0;
}
else
{
int q = st[p].next[c];
if (st[p].len + 1 == st[q].len)
{
st[cur].link = q;
}
else
{
int clone = sz++;
st[clone].len = st[p].len + 1;
st[clone].next = st[q].next;
st[clone].link = st[q].link;
for ( ; p != -1 && st[p].next[c] == q; p = st[p].link)
{
st[p].next[c] = clone;
}
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
inline int LCS(string A, string B, string C)
{
int lenA = sze(A);
int lenB = sze(B);
int lenC = sze(C);
memset(occ, 0, sizeof occ);
memset(cumocc, 0, sizeof cumocc);
memset(tree, -1, sizeof tree);
kmp(B, C);
build(1, 0, lenB-1);
init();
for (int i = 0; i < lenA; i++) sz_extend(A[i]);
int v = 0;
int l = 0;
int best = 0;
int bestPos = 0;
for (int i = 0; i < lenB; i++)
{
while (v && !st[v].next.count(B[i]))
{
v = st[v].link;
l = st[v].len;
}
if (st[v].next.count(B[i]))
{
v = st[v].next[ B[i] ];
l++;
}
int newl = 0;
if (l < lenC)
{
newl = l;
}
else
{
int bgn = i - l + 1;
int edd = i - lenC + 1;
segmentTree q = query(1, 0, lenB-1, bgn, edd);
if (q.lastocc == -1)
{
newl = l;
}
else
{
newl = i - q.lastocc;
}
}
if (newl > best)
{
best = newl;
bestPos = i;
}
}
// cout << B.substr(bestPos - best + 1, best) << endl;
return best;
}
int main()
{
//freopen("in.txt", "r", stdin);
FAST;
int tc;
cin >> tc;
for (int tcase = 1; tcase <= tc; tcase++)
{
cin >> A >> B >> C;
cout << LCS(A, B, C) << endl;
}
}
