All submissions for this problem are available.
Mr. Sinha is a intelligent guy and recently he got a very high package job offer. After this, he also got committed with a beautiful girl. But,before the commitment day, Mr. Sinha was challenging himself by manipulating a string with some other string. As challenges always teach you something, he was very close to learn to find the number of times a string W occur in a string S.
Mr. Sinha loves to think some more bigger thing. So, he was willing to know that the possible number of consecutive substrings of S which are good to a given string W.
Strings A and B are called good strings if you can rotate one string, say A, to get the other one, B. 'Rotate' here means 'to take some consecutive chars (maybe zero) from the starting of a string and put them back at the end of the string in the same order'. For example, string "apple" can be rotated to string "leapp". We can take characters "app" from the beginning and put them at the end of "le".
You are given string S and N strings Wi . For each string Wi , Help Mr. Sinha to find number of consecutive substrings of S are good toWi , as Mr. Sinha is busy with his love.
The first line contains a non-empty string S.
The second line contains an integer N --- the number of queries. Then N lines follow: the i-th line contains the string Wi --- the string for the i-th query. The total length of Wi is less than or equal to 10^6 characters.
For each query Wi print a single integer that shows how many consecutive substrings of S are good to Wi . Print the answers to the queries in the order they are given in the input.
In this problem, strings only consist of lowercase English letters.
Length of string S is not greater than 10^6.
Input: yxxyxxyxxx 5 x yx yxx xxyxx xxyx Output: 7 5 7 3 5
|Time Limit:||1 - 1.2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.