×

# Hackerearth AVI Hiring Challenge

 0 Hey, Can somebody help with this problem? Expected Solution - O(n) asked 06 Nov '17, 00:41 4★anushi 246●1●7 accept rate: 15%

 0 int calculate (string s) { int ans = 0; string s1,s2; for(int i=0;i
 0 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. answered 06 Nov '17, 08:52 5★apptica 939●2●10 accept rate: 17% 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★
 0 I solved this using hashing , you can check whether hash of both string are equal or not in O(1) after precomputation. answered 06 Nov '17, 11:02 34●2●3●8 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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