I’m trying to solve this problem and it seems like my solution is correct. but it gives WA on SPOJ after the 12th test case. Can someone guide me on how to solve this problem? Or check what I’m missing in my code. I have used some comments to explain what I’m trying to do at that step.
Problem Link: https://www.spoj.com/problems/BLHETA/
My Solution:
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<string.h>
#include<queue>
#include<map>
#include<stack>
#include<assert.h>
#include<unordered_map>
#include<algorithm>
//#define int long long
#define TEST(T) int T; cin >> T; while(T--)
#define F first
#define S second
#define VI vector<int>
#define VII vector<VI>
#define PB push_back
#define PF push_front
#define POB pop_back
#define PII pair<int,int>
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x << " is: " << x << endl
#define sz(z) (int)(z).size()
#define REP(i,a,Limit) for(int i = (a);i < (Limit); i++)
#define REPI(i,a,Limit) for(int i = (a); i > (Limit); i--)
#define PI acos(-1.0)
#define sync std::ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long
using namespace std;
const ll sp[2] = { 31,29 };
const ll mod[3] = { 1000000007,1000000009,998244353 };
// input assumed to be in range [0....m-1]
inline ll add(ll a, ll b, ll m) { a += b; if (a >= m) a -= m; return a; }
inline ll sub(ll a, ll b, ll m) { a -= b; if (a < 0) a += m; return a; }
inline ll mul(ll a, ll b, ll m) { a *= b; return a % m; }
const int MAXN = 10010;
int nxt[MAXN][26];
int slink[MAXN];
int olink[MAXN];
bool leaf[MAXN];
int id[MAXN];
int p[100010];
int lenid[100010];
int state[100010];
int ts = 0;
int find_par(int a) {
if (a == -1) {
return -1;
}
if (a == p[a]) {
return a;
}
return p[a] = find_par(p[a]);
}
void add(string& pat, int i) {
int curr_node = 0, c;
for (auto ch : pat) {
c = ch - 'A';
if (nxt[curr_node][c] == -1) {
nxt[curr_node][c] = ts++;
}
curr_node = nxt[curr_node][c];
}
leaf[curr_node] = true;
id[curr_node] = i;
}
void automate() {
queue < pair<int, PII> > q;// contains information as { character, {previous_node , current_node}}.
// on edge label 'character' we can go to current_node from previous_node
REP(c, 0, 26) {
if (nxt[0][c] != -1) {
slink[nxt[0][c]] = 0;
q.push({ c,{0,nxt[0][c]} });
}
}
// suffix links and output links are assigned in increasing order of string size using bfs
while (!q.empty()) {
pair<int, PII> pt = q.front();
q.pop();
int c = pt.first;
int prev_node = pt.second.first;
int curr_node = pt.second.second;
if (slink[curr_node] == -1) { // set suffix links
int x_node = slink[prev_node];
while (x_node != -1 && nxt[x_node][c] == -1) {
x_node = slink[x_node];
}
slink[curr_node] = (x_node == -1) ? 0 : nxt[x_node][c];
}
if (olink[curr_node] == -1) { // set output links
if (leaf[slink[curr_node]]) {
olink[curr_node] = slink[curr_node];
}
else {
olink[curr_node] = olink[slink[curr_node]];
}
}
if (leaf[curr_node]) {
// if more than 1 spells match at current_node
// we only need to store the index of first spell in spell book
if (olink[curr_node] != -1 && id[olink[curr_node]] < id[curr_node]) {
id[curr_node] = id[olink[curr_node]];
}
}
REP(c, 0, 26) {
if (nxt[curr_node][c] != -1) {
q.push({ c,{curr_node,nxt[curr_node][c]} });
}
}
}
}
void scan_text(const string& t) {
int curr_node = 0, c;
REP(i, 0, sz(t)) {
c = t[i] - 'A';
while (nxt[curr_node][c] == -1 && curr_node != 0) {
curr_node = slink[curr_node];
}
if (nxt[curr_node][c] != -1) {
curr_node = nxt[curr_node][c];
if (leaf[curr_node]) {
int len = lenid[id[curr_node]]; // len is the length of pattern at index id[curr_node] in spell book
int d = i;
// find_par(d) will find the previous undeleted character in text starting from d to 0 (both inclusive)
// if there are not any undeleted char it will return -1
while (len) {
d = find_par(d);
len--;
p[d] = find_par(d - 1); // delete this char & set it's parent to next_undeleted character.
}
}
if (find_par(i) != i) { // if current char is deleted i.e. match found at this curr_node
// change the curr_node accordingly.
curr_node = find_par(i) == -1 ? 0 : state[find_par(i)];
// find_par(i) returned -1 means there is not any character before index i, so curr_node is set 0
// otherwise state[] array is used to get the currect state
}
}
// to mark state after ith character
// cuz when we come back to this index we can take this state as initial state.
state[i] = curr_node;
}
}
signed main() {
sync;
memset(slink, -1, sizeof(slink));
memset(olink, -1, sizeof(olink));
memset(leaf, false, sizeof(leaf));
memset(nxt, -1, sizeof(nxt));
memset(id, -1, sizeof(id));
ts = 1;
REP(i, 0, MAXN) {
p[i] = i;
}
string text, pat;
cin >> text;
int q;
cin >> q;
REP(i, 0, q) {
cin >> pat;
add(pat, i); // adding strings in trie
lenid[i] = sz(pat);
}
automate(); // trie automaton
scan_text(text); // scan text
REP(i, 0, sz(text)) {
// if a char is not deleted then it will have the parent set to itself
if (i == find_par(i)) {
cout << text[i];
}
}
return 0;
}
Thank you for giving me your time!