Hey,
Can somebody help with this problem?
Expected Solution - O(n)
int calculate (string s) {
int ans = 0;
string s1,s2;
for(int i=0;i<s.length()-1;i++) {
s1 = s.substr(0,i+1);
s2 = s.substr(i+1,i+1);
if(s1 == s2)
ans++;
}
return ans;
}
It is simple. For every index in the string let F[i] denotes what is the length of longest prefix of the string that matches the substring of the string that starts at index i. Now you have to count total indices such that F[i] = i - 1 . This is because dividing by power of the 10 generates a prefix of the string. You can use Z algorithm for that.
For every i this will take O(n) for comparison hence O(n^2).If you meant something different please explain…
All operations defined inside for loop (substr & ==) takes O(length of string) hence in worst case it would lead O(n^2).
Z algorithm can do this in O(n) time for all the indexes. Just have a read of that.
I solved this using hashing , you can check whether hash of both string are equal or not in O(1) after precomputation.