Module: Función de prefijo, función Z


Problem

1/10

(C++) Búsqueda de subcadenas, KMP, variante trivial: Inicio

Theory Click to read/hide

Para resolver este problema, la enumeración habitual no funcionará, porque sus asintóticas serán O(t*s). Por lo tanto, para las tareas de búsqueda de subcadenas, se utiliza el algoritmo KMP (Knuth-Morris-Pratt).
Para implementar este algoritmo se utiliza la función de prefijo de cadena, esta es una matriz de números de longitud n (strong>s longitud), en la que cada elemento es la  longitud máxima del mayor sufijo propio de la subcadena s, coincidiendo con su prefijo. Por ejemplo:
  Línea Función de prefijo Nota abababcab 0 0 1 2 3 4 0 1 2   abcabcd 0 0 0 1 2 3 0   aabaaab 0 1 0 1 2 2 3  
Algoritmo de función de prefijo trivial con asintóticas O(n^3):

vector<int> función_prefijo (cadena s) {
int n = (int ) s.longitud();
vector<int>pi(n);
para (int i=0; i<n; ++i)
para (int k=0; k<=i; ++k)
si (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
regresarpi;
}

Y ahora necesitamos hacer una función de prefijo para una cadena de la forma: & nbsp; t + # + s, donde # es un carácter delimitador que claramente no está en el texto.  Al analizar los valores de la función de prefijo después del carácter separador correspondiente, se debe tener en cuenta que si el valor resultante es igual a la longitud de la subcadena deseada, entonces se encuentra su aparición. Por ejemplo, para la cadena "abababcab" y la subcadena deseada "abab", la función de prefijo será:
0 0 1 2 0 1 2 3 4 3 4 0 1 2 necesitamos analizar los elementos de la cadena correspondiente s:
1 2 3 4 3 4 0 1 2 - hay dos casos en los que el valor es 4 (4º y 6º), es decir longitud t,  como resultado, la respuesta debe escribirse: 4 - 4 (longitud t) & nbsp; = 0 y 6 - 4 = 2. Se puede ver que estas son las respuestas correctas y la cadena "abab" es en realidad una subcadena en la cadena "abababcab" en las posiciones 0 y 2.

 

Problem

Encuentre todas las apariciones de la cadena t en la cadena s.
 
Entrada
En la primera línea  se escribe la cadena s, la segunda línea contiene la cadena t. Ambas cadenas consisten solo en letras en inglés. Las longitudes de línea pueden oscilar entre 1 y 50 000 inclusive.
 
Salida
En la respuesta, muestra todas las apariciones de la cadena t en la cadena s en orden ascendente. La numeración de las posiciones de línea comienza desde cero.
 

 

Ejemplos

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
# Entrada Salida
1
abababcab
abab
 0 2
Write the program below 
#include <iostream>
#include <vector>
#include <string>

using namespace std;
vector<int> prefix_function(string s) {
	int n = (int)s.length();
	vector<int> pi(n);
	for (int i = 0; i < n; ++i)
		for (int k = 0; k <= i; ++k)
			if (s.substr(0, k) == s.substr(i - k + 1, k))
				pi[i] = k;
	return pi;
}

int main()
{
	string s, t;
	cin >> s >> t;
	s = t + '#' + s;
	vector<int> pi;
	pi = prefix_function(s);
   
      return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!