palindrome-count-1

Given a string S, count the number of non empty sub strings that are palindromes.
A sub string is any continuous sequence of characters in the string.
A string is said to be palindrome, if the reverse of the string is same as itself.
Two sub strings are different if they occur at different positions in S

Input
Input contains only a single line that contains string S.   

Output
Print a single number, the number of sub strings that are palindromes.

Constraints
1 ≤ |S| ≤ 50
S contains only lower case latin letters, that is characters a to z.

SAMPLE INPUT
dskjkd

SAMPLE OUTPUT
7

Explanation

The 7 sub strings are d, s, k, j, k, d, kjk.

Source: hackerearth | Difficulty: EASY
Tags: Fundamentals


Solutions:
from sys import *
def longestPallindrome(seq):
	seqLen = len(seq)
	l = [maxint] * (seqLen*2 + 1)
	nl = [0] * (seqLen*2 + 1)
	i = 0
	k = 0
	palLen = 0
	numPal = 0
	while i < seqLen:
		if i > palLen and seq[i - palLen - 1] == seq[i]:
			palLen += 2
			numPal += 1
			i += 1
			continue
		nl[k] = numPal
		l[k] = palLen
		k+=1
		#l.append(palLen)
		s = k - 2
		e = s - palLen
		flag = False
		for j in range(s, e, -1):
			d = j - e - 1
			if l[j] == d and not flag:
				palLen = d
				numPal = nl[j]
				flag = True
				oldk = k
			#l.append(l[j])
			# if d < l[j]:
			# 		l[k] = d
			# 		k+= 1
			# 		#l.append(d)
			# else:
			l[k],nl[k] = min((l[k],nl[k]),(l[j],nl[j]))
			#l[k] = l[j]
			k+= 1
			#l.append(l[j])
			#l.append(min(d, l[j]))
		if not flag:
			palLen = 1
			i += 1
		else:
			k = oldk

	l[k] = palLen
	nl[k] = numPal
	k += 1
	#l.append(palLen)
	lLen = k
	s = lLen - 2
	e = s - (2 * seqLen + 1 - lLen)
	for i in range(s, e, -1):
		d = i - e - 1
		l[k],nl[k] = (l[i],nl[i])
		#l[k],nl[k] = min((l[k],nl[k]),(l[i],nl[i]))				
		#l[k] = min(d,l[i])
		k+= 1
		#l.append(min(d, l[i]))
	return l,nl

def main():
	s = input()
	(l,nl) =  longestPallindrome(s)
	print(sum(nl) + len(s))
main()


def reverse(s,i,f):
	a=""
	b=""
	for j in range(i,f):
		b+=s[j]
	for j in range(f-1,i-1,-1):
		a+=s[j]
	if(a==b and i!=f):
		return 1
	return 0
def count(s):
	i=-1
	total=0
	while(i<len(s)):
		i+=1
		f=len(s)
		while(i<=f):
			if(reverse(s,i,f)):
					total+=1     
			f-=1
	return total
string=input()
print(count(string))


s=str(input())
count=0
for i in range(len(s)):
	for j in range(len(s)):
		p=s[i:j+1]
		q=p[::-1]
		if p==q and p!="":
			count=count+1
print(count)


def isPalindrome(s):
	lf = 0
	ri = len(s)-1
	while lf <= ri:
		if s[lf] != s[ri]:
			return 0
		lf += 1
		ri -= 1
	return 1

def getPalindromes(s):
	palindromes = []
	lf = 0
	ri = len(s)
	while lf <= ri:
		subri = lf+1
		while subri <= ri:
			t = s[lf:subri]
			if isPalindrome(t):
				palindromes.append(t)
			subri += 1
		lf += 1
	return palindromes


print(len(getPalindromes(input())))


s=input()
co=0
for i in range(0,len(s)):
	for j in range(i+1,len(s)+1):
		l= s[i:j]
		if(l==l[::-1]):
			co=co+1
print(co)			


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
s=input()
count=0
for i in range(1,len(s)):
	for j in range(0,len(s)-i+1):
		a=s[j:j+i]
		b=s[j:j+i][::-1]
		if a==b:
			count+=1
			
print(count)


str=input()
c=0;
for i in range(0,len(str)):

	for j in range(i+1,len(str)+1):
	
		if str[i:j] ==str[i:j][::-1]:
		
			
		
			
			c=c+1
		
			
			
print(c)


def palindrome(string):
	return string == string[::-1]
def substring_split(string):
	length = len(string)
	count = 0
	for j in range(length):
		for i in range(length-j):
			if palindrome(string[j:length-i]):
				count += 1
	return count
string = input()
print(substring_split(string))


ins = input().strip()
cnt = 0
for x in range(len(ins)):
	for y in range(x, len(ins)):
		curr =  ins[x:y+1]
		if curr == curr[::-1] and curr != "":
			cnt += 1
			
print(cnt)            
	

		
   


def lpc(s):
	if not s:
		return 0
	elif len(s) == 1:
		return 1
	elif s == s[::-1]:
		return len(s)/2+lpc(s[:-1])
	else:
		return lpc(s[:-1])

def rpc(s):
	if not s:
		return 0
	elif len(s) == 1:
		return 1
	elif s == s[::-1]:
		return len(s)/2+rpc(s[1:])
	else:
		return rpc(s[1:])

def pc (s):
	if not s:
		return 0
	elif len(s) == 1:
		return 1
	elif s == s[::-1]:
		return len(s)/2    + lpc(s[:-1]) + rpc(s[1:])
	else:
		return pc(s[1:-1]) + lpc(s[:-1]) + rpc(s[1:])

print(pc (input()))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
string=input()

def count(string):
	if not string:return 0
	count=0
	for i in range(len(string)):
		for j in range(i,len(string)):
			if string[i:j+1]==string[i:j+1][::-1]:
				count+=1
	return count
     
print(count(string))	


def substring(string):
	length=len(string)
	for i in range(length):
		for j in range(i+1,length+1):
			yield(string[i:j])
string=input()
substrings=list(substring(string))
count=0
for sub in substrings:
	if sub==sub[::-1]:
		count+=1
print(count)


s=input().strip()
cnt=0
for i in range(0,len(s)):
	for j in range(i+1,len(s)+1):
		if s[i:j]==s[i:j][::-1]:
			cnt+=1
print(cnt)


def find_all(iterable):
	s = tuple(iterable)
	for size in range(1, len(s)+1):
		for index in range(len(s)+1-size):
			yield iterable[index:index+size]

if __name__=='__main__':
	all_list = find_all(input())
	count = 0
	#lst = []
	for i in all_list:
		if i==i[::-1]:
			#lst.append(i)
			count += 1
	#print(lst)
	print(count)


# Palindrome count
def get_all_substrings(string):
	length = len(string)
	for i in range(length):
		for j in range(i + 1, length + 1):
			yield(string[i:j])
s=input()
sub_list=list(get_all_substrings(s))
count=0
for sub in sub_list:
	if sub==sub[::-1]:
		count+=1
print(count)