My approach :
- int sz = s.size(). String S = s + s. Find all positions of S where t occurs and (position <= sz that is ending position may be in the second occurrence of s in S but starting must be in the first one.) and store them in vector pos.
- Calculate vector pre, where pre[i] = number of occurrences of t in S, if we have starting position at index i then we know it ends at x = (i + t.size() - 1) so pre[x]++. and also we should check for x = (i + sz + t.size() - 1) (as the same will occur for the second s in S but for some occurrences ending point is in the next s, those we exclude because we don’t have any 3rd s in S).
- let’s say our according to our query we have “codecode…codeco” and s = “code”, then, we will divide into two parts - 1) “codecode…code” + “codeco”. 2nd part will always be 1 full s + remaining. Then answer = pos.size() * (number of times s occurred in 1) + pre[ length of 2 ].
code : link