Module: プレフィックス機能、Z機能


Problem

1/10

(C++) 部分文字列検索、KMP、自明なバリアント: 開始

Theory Click to read/hide

この問題を解決するには、通常の列挙は機能しません。その漸近線はO(t*s) になります。したがって、部分文字列検索タスクには、KMP (Knuth-Morris-Pratt) アルゴリズムが使用されます。
このアルゴリズムを実装するには、文字列プレフィックス関数が使用されます。これは長さ n (strong>s) の数値の配列であり、各要素は最大長になります。部分文字列 s の最大の独自の接尾辞を、その接頭辞と一致させます。例:
 

<本体>
O(n^3) 漸近線を持つ自明なプレフィックス関数アルゴリズム:

ベクトル<int> prefix_function (文字列 s) {
int n = (int ) s.length();
ベクトル<int>pi(n);
の (int i=0; i<n; ++i)
の (int k=0; k<=i; ++k)
if (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
円周率を返します。
}

次に、次の形式の文字列に対するプレフィックス関数を作成する必要があります。 t + # + s。# は明らかにテキストに含まれていない区切り文字です。対応する区切り文字の後のプレフィックス関数の値を分析すると、結果の値が目的の部分文字列の長さに等しい場合、その出現が検出されることに注意してください。たとえば、文字列「abababcab」の場合、および目的の部分文字列「abab」の場合、プレフィックス関数は次のようになります。
0 0 1 2 0 1 2 3 4 3 4 0 1 2対応する文字列 s の要素を解析する必要があります。
1 2 3 4 3 4 0 1 2 - 値が 4 になるケースが 2 つあります ( 4th と 6th )。長さ t、 その結果、答えは 4 - 4 (長さ t) と書く必要があります。 = 0 および 6 - 4 = 2。これらが正しい答えであり、文字列「abab」が正しい答えであることがわかります。実際には、文字列「abababcab」の部分文字列です。位置0と2にあります。

 

Problem

文字列 s 内の文字列 t の出現箇所をすべて検索します。
 
入力
最初の行で 文字列 s が書き込まれ、2 行目には文字列 t が含まれます。どちらの文字列も英字のみで構成されています。行の長さの範囲は 1 から 50,000 までです。
 
出力
応答では、文字列 s 内の文字列 t のすべての発生を昇順で出力します。行位置の番号付けはゼロから始まります。
 

 

例
ライン プレフィックス関数 メモ
アババブカブ 0 0 1 2 3 4 0 1 2  
abcabcd 0 0 0 1 2 3 0  
アバアブ 0 1 0 1 2 2 3  
<頭> <本体>

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++
# 入力 出力
1
アババブカブ
アバブ
 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!