Recently i encountered this problem Make It Through Your Way. I am not able to figure out why this code passes , i think it should give TLE. Link to code

Here each '.' can be called multiple times with values [0,v]. so it will increase the complexity to a large factor but still this code passes. Can anybody give me a proper analysis of time complexity of this code.

Thanks.

I was wondering if the Z value (LCP(0,i)) array of Z-Algorithm can be computed using KMP.
I need it for this problem :- http://www.spoj.com/problems/PRETILE/

I tried this problem using KMP and Matrix exponentiation, but got an WA and i'm unable to find the cases on which my solution fails.

This is the problem Link :- http://lightoj.com/volume_showproblem.php?problem=1268

In short this problem asks you to find out how many strings you can generate of length N that doesn't contain a given string(suppose the string be called "pat") as substring. The allowed characters are also given to you in the form of another string. 1 <= N <= 10^9 and 1 <= length(pat) <= 50.

My approach to the problem is to generate a matrix ans[length(pat)-1][length(pat)-1] in which each entry (i,j) corresponds to number of strings of length N generated if before the start of the string the pie value (pie value as in KMP algo which denotes the longest prefix which is also a suffix) was "i" and after the end of the string the pie value is "j". So by counting the entries in the table ans[0][k] where 0 <= k < length(pat) we can get the final answer.

Now to get the matrix ans we can use matrix exponentiation. we can determine value for each entry (i,j) if N = 1 using KMP and then apply matrix exponentiation to generate final matrix for given N.

This is my solution and it's giving WA http://ideone.com/3PTR9S

Please tell if i'm missing something or if there's a bug in my code . Thanks.

Note :- This problem requires you to compute the answer modulo 2^32.

I was trying to solve this problem but i am getting WA on test 19. I'm not able to figure out the bug in my code.

Problem Link :- http://acm.sgu.ru/problem.php?contest=0&problem=284

I have used the approach explained here :- http://e-maxx.ru/algo/prefix_function translated version here :- http://translate.yandex.net/tr-url/ru-en.en/e-maxx.ru/algo/prefix_function

I have first computed the pie function(KMP) of the pattern to search. Then i have used the approach explained in the given link. (The Build Machine prefix function part).

This is my code :- http://ideone.com/NcBqKX

I was trying this question and i got WA at case 3. Problem Link:- http://acm.timus.ru/problem.aspx?space=1&num=1713

My approach includes constructing a suffix array on string formed by concatenating all the strings(commands) given in the input.

Then for each index belonging to the command i am calculating the max value of LCP that can be formed using other indexes belonging to other commands. For doing that i am calculating the closest indexes to that index not belonging to the same command using the Array sorted in order of suffixes.

For any command the answer of that command will be the smallest value of LCP of indexes belonging to that command described as above .

I am unable to find any bug . So please Help ......

This is my code :- http://ideone.com/8veKxE

This is my first post , so kindly ignore any mistakes .