21396. Taklu Kuddus Wrong Answer

[luckymastermin]

Hi All,

I was trying this problem http://www.spoj.com/problems/TKUDDUS/ using Python and getting wrong answer.

Algorithm:: I am finding the index of the given string in main string and storing all index in a list.
Again I am using binary search to find the the number number of string in the given range.

Below is My code.

Thanks
[bbone=python,750]import math,sys,re,bisect
def findstr(S,T):
starts = [match.start() for match in re.finditer(re.escape(S), T)]
return starts
T=input()
for cs in range(T):
mains= str(sys.stdin.readline().strip())
str1 = str(sys.stdin.readline().strip())
c=findstr(str1,mains)
l=len(str1)
print"Case %d:"%(cs+1)
C=[]
for a in c:
C.append(a+l-1)
#print C
Q=input()
for q in range(Q):
x,y = map(int,(sys.stdin.readline()).strip().split())
X = bisect.bisect_right(C,x)
Y = bisect.bisect_right(C,y)
print Y-X

[/bbone]

[leppyr64]

non-overlapping

[luckymastermin]

non-overlapping

Yes I am doing same thing
here is one case
[bbone=text,751]1
abababababbaa
aba
3
0 12
1 6
6 12
output:
Case 1:
2
2
0
aba is string and only two string between (0 6) and (0 12) and not string between (6 12).
[/bbone]

[leppyr64]

1
ababababc
abab
1
2 8

[luckymastermin]

Thanks Lappy .

Problem was with my binary search Now corrected but getting TLE

here is my updated code

[bbone=python,752]import math,sys,re,bisect
def findstr(S,T):
starts = [match.start() for match in re.finditer(re.escape(S), T)]
return starts
T=input()
for cs in range(T):
mains= str(sys.stdin.readline().strip())
str1 = str(sys.stdin.readline().strip())
c=findstr(str1,mains)
l=len(str1)
print"Case %d:"%(cs+1)
C=[]
for a in c:
C.append(a+l-1)
#print C
Q=input()
for q in range(Q):
x,y = map(int,(sys.stdin.readline()).strip().split())
X = bisect.bisect_left(c,x)
Y = bisect.bisect_right(C,y)
print Y-X

[/bbone]

[leppyr64]

I can't help you with TLE in Python. numerix should be a round at some point.