Module: Önek işlevi, Z işlevi


Problem

5 /10


Z işlevi

Theory Click to read/hide

Z-fonksiyonu
S dizisinden
Z-fonksiyonu - her elemanı Z olan Z dizisi [i ], S dizgisinde i konumundan başlayan alt dizgenin en uzun önekine eşittir, bu aynı zamanda tüm Z. Sıfır konumundaki Z-fonksiyonunun değeri genellikle sıfırdır veya tüm dizenin uzunluğudur.
Zorluk
O(|S| ^ 2) veya O(|S|).
 
S - P dizisinden önek işlevi, her elemanı P[i] dizinin en uzun sonekine eşittir. S dizgisindeki < code>i konumundan başlayan bir alt dizgi; bu aynı zamanda S dizgisinin tamamının soneki. Sıfır konumundaki P-fonksiyonunun değeri genellikle sıfırdır veya tüm dizenin uzunluğudur. 
Zorluk
O(|S| ^ 2) veya O(|S|).
 
O(|S| ^ 2) için Z işlevini ve önek işlevini uygulamaya çalışın .

Problem

İki dize verilir - S ve T. Göreviniz, S dizgisinin i-inci önekinin T dizgisindeki geçiş sayısını görüntülemektir.

Girdi
İlk satırda k bulunur - sorgu sayısı (\(k <= uzunluk( S)\)), dize S< /code> ve T dizesi. Ardından, S dizgisinin i-inci önekinin dizgisinde tekrarlanma sayısı için bir istek olan k istekleri girilir. >T.

Çıktı
k satırlık sorgu yanıtı çıktısı

 

Örnekler

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Girdi Çıktı
1
2 ali balimalı
3
0
 2
8