113B - Petr#

I know limits are big and no suffix array implementation is needed but i am trying to learn about S.A. so it would be nice if someone could help me about this problem.

My idea about the problem is finding each occurrence of the end string and mark these in a array with a 1. Then prefix sum that array for range sum queries. After that on the suffix array of t+'#'+Sbegin iterate over the sorted suffixes which have Sbegin as a prefix to find how many times Send occurs after beginning of each one(using the prefix sum thingy) and use lcp for not counting re-occurrences. I am not sure if this works but i have tried to code this and it failed on test case 24. It might have bugs i am new at S.A. coding. 10309125

Is it possible to solve this problem this way or with Suffix Array? (I didnt used counting sort but with counting sort this should have O(nlogn) complexity.)