Problem
दिया गया एक गैर-खाली स्ट्रिंग S जिसकी लंबाई N \(10^6\)। हम मानेंगे कि स्ट्रिंग के तत्वों को 1 से N तक क्रमांकित किया गया है।
स्ट्रिंग में i वर्ण की प्रत्येक स्थिति के लिए, हमें उस सबस्ट्रिंग में दिलचस्पी होगी जो उस स्थिति पर समाप्त होता है और पूरे स्ट्रिंग की शुरुआत से मेल खाता है। सामान्यतया, ऐसे कई सबस्ट्रिंग होंगे, कम से कम दो। उनमें से सबसे लंबे समय की लंबाई i है, हमें इसमें कोई दिलचस्पी नहीं होगी। और हम इस तरह के शेष सबस्ट्रिंग्स में से सबसे लंबे समय तक रुचि लेंगे (ध्यान दें कि ऐसा सबस्ट्रिंग हमेशा मौजूद होता है — चरम मामले में, अगर कुछ और नहीं मिलता है, तो एक खाली सबस्ट्रिंग काम करेगा)।
उपसर्ग फ़ंक्शन का मान \(\pi[i]\) इस सबस्ट्रिंग की लंबाई होगी।
प्रीफिक्स फ़ंक्शन का उपयोग विभिन्न स्ट्रिंग प्रोसेसिंग एल्गोरिदम में किया जाता है। विशेष रूप से, इसका उपयोग एक स्ट्रिंग की दूसरी स्ट्रिंग ("पाठ में एक पैटर्न की खोज") की घटना को खोजने की समस्या को जल्दी से हल करने के लिए किया जा सकता है।
1 से N तक \(\pi[i) की गणना करने के लिए सभी i के लिए आवश्यक है ] \)।
इनपुट
लंबाई की एक स्ट्रिंग N, \(0 < N <= 10^6\), जिसमें छोटे लैटिन अक्षर हैं ।
आउटपुट
आउटपुट <कोड>एन नंबर — प्रत्येक स्थिति के लिए उपसर्ग फ़ंक्शन मान, रिक्त स्थान द्वारा अलग किए गए।
उदाहरण
<टेबल क्लास = "टेबल-बॉर्डर्ड टेबल-लिस्ट-टेस्ट टेबल-एसएम टेबल-स्ट्राइप्ड">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
अब्रकदबरा |
0 0 0 1 0 1 0 1 2 3 4 |