You are not logged in. Please login at www.codechef.com to post your questions!

×

Hackerearth AVI Hiring Challenge

Hey,

Can somebody help with this problem?

Expected Solution - O(n) alt text

asked 06 Nov '17, 00:41

anushi's gravatar image

4★anushi
24617
accept rate: 15%


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;
  }
link

answered 06 Nov '17, 01:10

shukrant's gravatar image

4★shukrant
1214
accept rate: 22%

edited 06 Nov '17, 01:13

All operations defined inside for loop (substr & ==) takes O(length of string) hence in worst case it would lead O(n^2).

(06 Nov '17, 09:15) anushi4★

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.

link

answered 06 Nov '17, 08:52

apptica's gravatar image

5★apptica
939210
accept rate: 17%

edited 06 Nov '17, 08:52

For every i this will take O(n) for comparison hence O(n^2).If you meant something different please explain..

(06 Nov '17, 09:14) anushi4★

Z algorithm can do this in O(n) time for all the indexes. Just have a read of that.

(06 Nov '17, 09:37) apptica5★

I solved this using hashing , you can check whether hash of both string are equal or not in O(1) after precomputation.

link

answered 06 Nov '17, 11:02

geeky_coder's gravatar image

4★geeky_coder
34238
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×398
×349
×10

question asked: 06 Nov '17, 00:41

question was seen: 407 times

last updated: 06 Nov '17, 11:02