Question

Two challenging questions???
1. To find the longest palindrome in a given string?
2. To find the longest non repeated sub string in a given string?

both the thing needs, O(n)...? any solution guys??

Answer 1

something really challenging guys ....

Answer 2

That's pretty tough. I'd work on first writing down the necessary algorithm for determining each of them. Then determine the recurrence relation and find O(n) that way.

Answer 3

for the first one, i think this way

first let n the lenght of the string, and supose it is implemented as an array (this would make constant operations)

half = n/2
for(i = 0 ; i<half; i++)
if(string[i] != string[k-i-1]) return false; //that -1 depends on the lenguage, but in C i think its ok
return true;

this make this O(n/2)

the second one its harder u need to probably use an propierty and make a recursion, ill think about

Answer 4

instead of k is n

Answer 5

oh, so you are working on project euler...
The first one, at least related...is in assembler:
; maximum palidrome
xor ebx, ebx

; two three digit numbers
mov esi, 999
_0: mov edi, 999
_1: ; multiplied together
mov ecx, esi
imul ecx, edi

; Is palindrome?
push ecx
push ecx
push ecx
fild DWORD PTR [esp]
fbstp TBYTE PTR [esp]

; five or six digits
mov edx, DWORD PTR [esp]
mov eax, edx
and edx, 0F0F0Fh
and eax, 0F0F0F0h
cmp DWORD PTR [esp], 100000h
jc five
; six digits
; 00 AB CD EF
shl edx, 4+8
shl eax, 4
or eax, edx
bswap eax
; 00 FE DC BA
jmp check

five: ; 00 0A BC DE
shl edx, 8
shl eax, 16
or eax, edx
bswap eax
; 00 0E DC BA
check: cmp DWORD PTR [esp], eax
lea esp, [esp + 12]
jne @F
cmp ebx, eax
cmovc ebx, eax
@@: dec edi
cmp edi, 99
jne _1
dec esi
cmp esi, 99
jne _0

The second one: That is one I have no idea on.