Skip to Content
CTRL K

Frequency of String

El editorial oficial  menciona una solución usando un autómata de Aho-Corasick construido sobre los strings de las consultas. Recorremos el string inicial sobre el autómata para localizar todas las posiciones de ocurrencia de cada consulta. La respuesta se puede identificar fácilmente para cada consulta usando una ventana deslizante.

De forma más intuitiva, en lugar de construir un autómata de Aho-Corasick sobre las consultas, construyamos un autómata de sufijos sobre el string de entrada. Como antes, necesitaremos todas las posiciones de ocurrencia.

Para un estado ss, sea pos[s]pos[s] la posición final de la primera ocurrencia de cualquier string que corresponde al estado ss.

  • Cuando creamos un estado nuevo ss, entonces pos[s]=len[s]−1pos[s] = len[s] - 1
  • Cuando clonamos el estado tt para crear un estado ss, entonces pos[s]=pos[t]pos[s] = pos[t] Con este método, podemos inicializar pospos fácilmente sin complejidad extra. Sea occPocc_P el conjunto de posiciones donde un string PP empieza en el string. Si el estado ss corresponde a PP, entonces claramente (pos[p]−∣P∣+1)∈occP(pos[p] - |P| + 1) \in occ_P. Para hallar el resto de las posiciones de ocurrencia, podemos aprovechar la estructura del autómata de sufijos.

Todos los estados en los que PP es un sufijo son candidatos para occPocc_P. Así, simplemente hacemos un BFS/DFS sobre el árbol de enlaces de sufijo (suffix-link tree), o el árbol formado al construir un árbol a partir de los enlaces de sufijo y enraizado en el estado inicial, empezando desde el estado al que llegamos cuando recorremos PP sobre el autómata de sufijos. Hay un detalle técnico: más de un estado puede tener la misma posición de ocurrencia. En concreto, esto ocurre solo con estados clonados; por eso redefinimos pos[s]=−1pos[s] = -1 para todos los estados clonados ss.

Podemos preprocesar todas las consultas y resolverlas todas con un único BFS/DFS.

Complejidad temporal: O(mmlog⁡n)\mathcal{O}(m \sqrt{m} \log n)

#include <bits/stdc++.h>
using namespace std;
 
using pii = pair<int, int>;
 
// BeginCodeSnip{Suffix Automaton}
/**
 * Genera el autómata de sufijos de un string dado
 * Complejidad: O(|S|)
 */
struct SuffixAuto {
	struct State {
		int len, link, pos;
		int next[26];
		State(int len = 0, int link = -1, int pos = -1)
		    : len(len), link(link), pos(pos) {
			memset(next, -1, sizeof(next));
		}
	};
 
	vector<State> states;
 
	SuffixAuto() {}
 
	SuffixAuto(const string &S) {
		states.reserve(2 * S.size());
		last = state();
		for (char c : S) { extend(c); }
	}
 
	void extend(char l) {
		int c = encode(l);
		int cur = state(states[last].len + 1, -1, states[last].len), P = last;
		while (P != -1 && states[P].next[c] == -1) {
			states[P].next[c] = cur;
			P = states[P].link;
		}
		if (P == -1) {
			states[cur].link = 0;
		} else {
			int Q = states[P].next[c];
			if (states[P].len + 1 == states[Q].len) {
				states[cur].link = Q;
			} else {
				int C = state(states[P].len + 1, states[Q].link, -1);
				copy(states[Q].next, states[Q].next + 26, states[C].next);
				while (P != -1 && states[P].next[c] == Q) {
					states[P].next[c] = C;
					P = states[P].link;
				}
				states[Q].link = states[cur].link = C;
			}
		}
		last = cur;
	}
 
	int run(string &P) {
		int s = 0;
		for (char _c : P) {
			int c = encode(_c);
			s = states[s].next[c];
			if (s == -1) { return -1; }
		}
		return s;
	}
 
  private:
	int last;
 
	int encode(char c) { return c - 'a'; }
 
	inline int state(int len = 0, int link = -1, int pos = -1) {
		states.emplace_back(len, link, pos);
		return states.size() - 1;
	}
};
// EndCodeSnip
 
const int MAXN = 1e5 + 1;
 
string S;
SuffixAuto sa;
 
// respuesta de la consulta
int Q, ans[MAXN];
// consultas por estado
vector<pii> queries[MAXN];
// árbol de enlaces de sufijo (a lo sumo 2 * |S| nodos)
vector<int> suffix_link_tree[MAXN * 2];
 
vector<int> ord;  // nodos visitados en el dfs
 
void dfs(int u) {
	int l = ord.size();
	if (sa.states[u].pos != -1) { ord.PB(sa.states[u].pos); }
 
	for (int v : suffix_link_tree[u]) { dfs(v); }
 
	if (queries[u].size()) {
		int r = ord.size();
		sort(ord.begin() + l, ord.end());
		for (auto [q, K] : queries[u]) {
			int t = INT_MAX;
			for (int i = l; i + K - 1 < r; i++) { t = min(t, ord[i + K - 1] - ord[i]); }
			if (t != INT_MAX) {
				ans[q] += t;
			} else {
				ans[q] = -1;
			}
		}
	}
}
 
int main() {
	cin >> S >> Q;
	sa = SuffixAuto(S);
	for (int i = 1; i < sa.states.size(); i++) {
		suffix_link_tree[sa.states[i].link].push_back(i);
	}
	for (int i = 0; i < Q; i++) {
		int K;
		string P;
		cin >> K >> P;
		int s = sa.run(P);
		if (s == -1) {
			ans[i] = -1;
		} else {
			queries[s].EB(i, K);
			ans[i] = P.size();
		}
	}
 
	dfs(0);
 
	for (int i = 0; i < Q; i++) { cout << ans[i] << '\n'; }
}
Fundamentos