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.