Module: उपसर्ग फ़ंक्शन, Z फ़ंक्शन


Problem

1/10

(C++) सबस्ट्रिंग खोज, KMP, तुच्छ संस्करण: प्रारंभ करें

Theory Click to read/hide

इस समस्या को हल करने के लिए सामान्य गणना काम नहीं करेगी, क्योंकि इसके स्पर्शोन्मुख O(t*s) होंगे। इसलिए, सबस्ट्रिंग खोज कार्यों के लिए, KMP (नथ-मॉरिस-प्रैट) एल्गोरिथ्म का उपयोग किया जाता है।
इस एल्गोरिथ्म को लागू करने के लिए, स्ट्रिंग उपसर्ग फ़ंक्शन का उपयोग किया जाता है, यह लंबाई n (strong>s लंबाई) की संख्याओं की एक सरणी है, जिसमें प्रत्येक तत्व  अधिकतम लंबाई है सबस्ट्रिंग s के सबसे बड़े स्वयं के प्रत्यय का, इसके उपसर्ग से मेल खाता हुआ। उदाहरण के लिए:
  <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स"> <शरीर> लाइन उपसर्ग समारोह ध्यान दें अबाबाबकैब 0 0 1 2 3 4 0 1 2   एबीसीबीसीडी 0 0 0 1 2 3 0   आबाआब 0 1 0 1 2 2 3  
O(n^3) asymptotics के साथ ट्रिवियल प्रीफ़िक्स फ़ंक्शन एल्गोरिद्म:

का उपयोग करके उत्पन्न किया गया

<पूर्व शैली = "मार्जिन-बाएं: 0 पीएक्स; मार्जिन-दाएं: 0 पीएक्स"> वेक्टर<int> उपसर्ग_फंक्शन (स्ट्रिंग एस) { int n = (int ) एस लंबाई (); वेक्टर<int> पाई (एन); के लिए (int i=0; i<n; ++i) के लिए (int k=0; k<=i; ++k) अगर (s.substr(0,k) == एस .substr(i-k+1,k)) pi[i] = k; वापसीपी; }

और अब हमें प्रपत्र की एक स्ट्रिंग के लिए एक उपसर्ग फ़ंक्शन बनाने की आवश्यकता है: & nbsp; t + # + s, जहां # एक सीमांकक वर्ण है जो पाठ में स्पष्ट रूप से नहीं है।  संबंधित विभाजक चरित्र के बाद उपसर्ग फ़ंक्शन के मूल्यों का विश्लेषण करते हुए, यह ध्यान दिया जाना चाहिए कि यदि परिणामी मान वांछित सबस्ट्रिंग की लंबाई के बराबर है, तो इसकी घटना पाई जाती है। उदाहरण के लिए, "abababcab" और वांछित सबस्ट्रिंग "अबाब", उपसर्ग समारोह होगा:
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 (चौथा और छठा) है, यानी लंबाई टी,  नतीजतन, उत्तर लिखा जाना चाहिए: 4 - 4 (लंबाई टी) & nbsp; = 0 और 6 - 4 = 2। यह देखा जा सकता है कि ये सही उत्तर हैं और स्ट्रिंग "अबाब" वास्तव में "abababcab" स्थिति 0 और 2 में।

 

Problem

स्ट्रिंग t की सभी घटनाओं को s में खोजें।
 
इनपुट
पहली पंक्ति पर  स्ट्रिंग s लिखा गया है, दूसरी पंक्ति में स्ट्रिंग t है। दोनों तारों में केवल अंग्रेजी अक्षर होते हैं। लाइन की लंबाई 1 से लेकर 50,000 तक शामिल हो सकती है।
 
आउटपुट
प्रतिक्रिया में, स्ट्रिंग t की सभी घटनाओं को बढ़ते क्रम में s में आउटपुट करें। लाइन पोजीशन की संख्या शून्य से शुरू होती है।
 

 

उदाहरण
<टेबल क्लास = "टेबल-बॉर्डर्ड टेबल-लिस्ट-टेस्ट टेबल-एसएम टेबल-स्ट्राइप्ड"> <सिर> <वें># <वें>इनपुट <वें>आउटपुट <शरीर> 1 <टीडी>
अबाबाबकैब
अबाब
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!