Module: Funzione prefisso, funzione Z


Problem

1/10

(C++) Ricerca di sottostringhe, KMP, variante banale: Start

Theory Click to read/hide

Per risolvere questo problema, la solita enumerazione non funzionerà, perché i suoi asintotici saranno O(t*s). Pertanto, per le attività di ricerca di sottostringhe, viene utilizzato l'algoritmo KMP (Knuth-Morris-Pratt).
Per implementare questo algoritmo, viene utilizzata la funzione prefisso stringa, che è un array di numeri di lunghezza n (strong>s length), in cui ogni elemento è la  lunghezza massima del suffisso più grande della sottostringa s, corrispondente al suo prefisso. Ad esempio:
 

Linea Funzione prefisso 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 banale per la funzione del prefisso con asintotici O(n^3):

vettore<int> funzione_prefisso (stringa s) {
int n = (int ) s.lunghezza();
vettore<int>pi(n);
per (int i=0; i<n; ++i)
per (int k=0; k<=i; ++k)
if (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
ritornopi greco;
}

E ora dobbiamo creare una funzione prefisso per una stringa della forma: & nbsp; t + # + s, dove # è un carattere delimitatore chiaramente non presente nel testo.  Analizzando i valori della funzione prefisso dopo il carattere separatore corrispondente, va notato che se il valore risultante è uguale alla lunghezza della sottostringa desiderata, viene trovata la sua occorrenza. Ad esempio, per la stringa "abababcab" e la sottostringa desiderata "abab", la funzione prefisso sarà:
0 0 1 2 0 1 2 3 4 3 4 0 1 2 dobbiamo analizzare gli elementi della stringa corrispondente s:
1 2 3 4 3 4 0 1 2 - ci sono due casi in cui il valore è 4 (4° e 6°), cioè lunghezza t,  di conseguenza, la risposta deve essere scritta: 4 - 4 (lunghezza t) & nbsp; = 0 e 6 - 4 = 2. Si può vedere che queste sono le risposte corrette e la stringa "abab" è in realtà una sottostringa nella stringa "abababcab" nelle posizioni 0 e 2.

 

Problem

Trova tutte le occorrenze della stringa t nella stringa s.
 
Input
Nella prima riga  viene scritta la stringa s, la seconda riga contiene la stringa t. Entrambe le stringhe sono composte solo da lettere inglesi. Le lunghezze delle righe possono variare da 1 a 50.000 inclusi.
 
Uscita
Nella risposta, mostra tutte le occorrenze della stringa t nella stringa s in ordine crescente. La numerazione delle posizioni di riga parte da zero.
 

 

Esempi
# Input Uscita
1
abababcab
aba
 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!