Module: Função de prefixo, função Z


Problem

1/10

(C++) Pesquisa de substring, KMP, variante trivial: Iniciar

Theory Click to read/hide

Para resolver este problema, a enumeração usual não funcionará, porque sua assimptótica será O(t*s). Portanto, para tarefas de pesquisa de substring, o algoritmo KMP (Knuth-Morris-Pratt) é usado.
Para implementar este algoritmo, a função string prefix é usada, esta é uma matriz de números de comprimento n (strong>s comprimento), em que cada elemento é o  comprimento máximo do maior sufixo próprio da substring s, correspondente ao seu prefixo. Por exemplo:
 

Linha Função de prefixo 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 função de prefixo trivial com O(n^3) assintótico:

vetor<int> função_prefixo (string s) {
int n = (int ) s.comprimento();
vetor<int>pi(n);
para (int i=0; i<n; ++i)
para (int k=0; k<=i; ++k)
se (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
retornarpi;
}

E agora precisamos fazer uma função de prefixo para uma string no formato: & nbsp; t + # + s, onde # é um caractere delimitador que claramente não está no texto.  Analisando os valores da função de prefixo após o caractere separador correspondente, deve-se observar que, se o valor resultante for igual ao comprimento da substring desejada, sua ocorrência será encontrada. Por exemplo, para a string "abababcab" e a substring desejada "abab", a função do prefixo será:
0 0 1 2 0 1 2 3 4 3 4 0 1 2 precisamos analisar os elementos da string correspondente s:
1 2 3 4 3 4 0 1 2 - há dois casos em que o valor é 4 (4º e 6º), ou seja, comprimento t,  como resultado, a resposta deve ser escrita: 4 - 4 (comprimento t) & nbsp; = 0 e 6 - 4 = 2. Pode-se ver que essas são as respostas corretas e a string "abab" é na verdade uma substring na string "abababcab" nas posições 0 e 2.

 

Problem

Encontre todas as ocorrências da string t na string s.
 
Entrada
Na primeira linha  a string s é escrita, a segunda linha contém a string t. Ambas as strings consistem apenas em letras em inglês. Os comprimentos de linha podem variar de 1 a 50.000 inclusive.
 
Saída
Na resposta, mostre todas as ocorrências da string t na string s em ordem crescente. A numeração das posições das linhas começa em zero.
 

 

Exemplos
# Entrada Saída
1
abababcab
abab
 0 2

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++
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!