Module: Präfix-Funktion, Z-Funktion


Problem

1/10

(C++) Suche nach Teilzeichenfolge, KMP, triviale Option: Start

Theory Click to read/hide

Um dies zu erreichen, wird eine normale Übernahme nicht möglich sein, da die Asymptomie eine Asymmetrie sein wird. O(t*s). Der Algorithmus der Kommission ' s (Knuta-Morrisa-Pratta) wird daher zur Unterkonstruktionssuche verwendet.
Dieser Algorithmus verwendet die Prefix-Funktion der Zeile, es ist eine Menge Chips lang. n(Länge der Linie Sin dem jedes Element die größte Länge der hauseigenen Souffix des Unterbaus ist Smit ihrem Präfix. Zum Beispiel:

StrengePräfix FunktionAnmerkung
Ababababab0 0 1 2 3 4 0 1 2
Abcabc0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Aabaaab0 1 0 1 2 3

Trivial-Algorithmus der Präfix-Funktion mit der Asymptomie O(n^3):

HTML generiert mit Hilite. ich 
Vektor/ination prefix_function (string s) {
in n = (seufzt)ins.length();
Vektor/ination Pi (n)
für (seufzt)in I= 0, i/n ++(i)
für (seufzt)in k.= 0, k:i) ++(k)
wenn (s.substr(s)0),k) == sync, berichtigt von elderman == s.substr(i)♪k.+ 1(k)
Pi[i] = k;
zurück Pi;
♪

Jetzt müssen wir einen präfix-funk für eine Artlinie machen: t + Swo # ein Streusymbol ist, das definitiv nicht im Text ist. Eine Analyse der Vorfix-Funktionswerte nach dem entsprechenden Teilersymbol zeigt an, dass, wenn der erhaltene Wert gleich der Länge der Unterstruktur ist, gefunden wird. Beispielsweise für die Bababcab-Linie und den Bababababab im Aufbau wird die Präfix-Funktion sein:
0 1 2 0 1 2 3 4 0 1 2 wird die ersten 5 Elemente abweisen, da wir eine Analyse der Elemente der entsprechenden Zeile s haben:
1 2 3 4 3 4 0 1 2 - es gibt zwei Fälle, in denen der Wert 4 (vier und sechste) beträgt, d.h. Länge t, aufgrund der Antwort, 4 - 4( Länge t) = 0 und 6 - 4 = 2. Es ist offensichtlich, dass dies die richtigen Antworten ist und die babab-Linie tatsächlich eine Unterzeile in der babcab-Linie in 0 und 2 ist.

Problem

Findet alle Vorkommen der t -Zeichenfolge in der s-Zeichenfolge.
 
Eingabe
In der ersten Zeile wird s geschrieben, in der zweiten Zeile wird t geschrieben. Beide Zeilen bestehen nur aus englischen Buchstaben. Die Zeilenlängen können im Bereich von 1 bis einschließlich 50.000 liegen.
 
Ausgabe
In der Antwort müssen Sie alle Vorkommen von t in der Zeichenfolge s in aufsteigender Reihenfolge ausgeben. Die Nummerierung der Zeilenpositionen beginnt bei Null.
 

 

Beispiele
№ Eingabe Ausgabe
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!