difdif

You are given a string S. Find the number of different substrings in S.

Input
One line containing a string S consisting of lowercase Latin letters.

Output
Output one integer - answer to the question.

Constraints
1 ≤ length of S ≤ 1200

SAMPLE INPUT
abc

SAMPLE OUTPUT
6

Difficulty: EASY
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
def cal(n):
	if n == 0 or n == 1:
		return 1
	return n*cal(n-1)

s = input()
dt = {}
for i in range(len(s)):
	for j in range(i,len(s)+1):
		#print s[i:j]
		if s[i:j] in dt :
			pass
		else:
			dt[s[i:j]] = 1

print(len(dt)-1)


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
x=input()
y=len(x)
m = {}
for i in range(0,y):
	k=x[i]
	m[k]=1
	for j in range(i+1,y):
		k = k+x[j]
		m[k]=1
print(len(m))


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

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

s=input()
l=[]
for i in range(len(s)):
	l.append(s[i])
	for j in range(i+1,len(s)):
		l.append(s[i:j])
	
	l.append(s[i:])
		


#print(l)
print((len(set(l))))


s=input()
sub=[]
n=len(s)
for i in range(0,n):
	for j in range(i,n):
		sub.append(s[i:j+1])
l=set(sub)

print(len(l))


from sys import stdin
S=stdin.readline().strip()
N=len(S)
out=N*(N+1)/2
for i in range(1,len(S)+1):
	for j in range(0,len(S)-i+1):
		sub=S[j:j+i]
		if(j !=S.rindex(sub)):
			out-=1
print(out)


string=input()
l=len(string)
res=l*(l+1)/2
s=set()
for i in range(l):
	for j in range(l-i):
		s.add(string[j:j+i+1])
print(len(s))


def substr(string):
	j=1
	a=set()
	while True:
		for i in range(len(string)-j+1):
			a.add(string[i:i+j])
		if j==len(string):
			break
		j+=1
		#string=string[1:]
	return a
	

	
print(len(substr(input().strip())))    
	
	


from collections import deque, defaultdict, Counter
from math import factorial
from fractions import gcd
from sys import stdin
from itertools import *
import heapq
import string
import re

	
def get():
	return testcase.next().strip()
	
def solve():
	pass
	

testcase = stdin

# code starts here
s = get()
print(len(set(s[i:j+1] for i in range(len(s)) for j in range(i, len(s)))))




string = input()
length = len(string)
l = []
for i in range(length):
	for j in range(i,length):
		l.append(string[i:j + 1])
print(len(set(l)))


s = input()
j=0
p=set()
for i in range(0,len(s)+1):
 	for j in range(1,len(s)+1):
 		p.add(s[i:j])
print(len(p)-1)
##print p
 	


st = input()
ans = set()
for i in range(len(st)):
    
	for j in range(i, len(st)):
		k = ""
		k = st[i:j+1]
		h = k
		ans.add(h)
print(len(ans))        
		


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def get_all_substrings(string):
	length = len(string)
	alist = []
	for i in range(length):
		for j in range(i,length):
			alist.append(string[i:j + 1]) 
	return alist

s = input()
lis = get_all_substrings(s)
se = set(lis)
lis = list(se)
print((len(lis)))


S = input()

if len(S) in range(1, 1200+1):
	l = [S[i:j] for i in range(len(S)) for j in range(i + 1, len(S) + 1)]
	print(len(list(set(l))))


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
'''print 'Hello World!'''
st=input()
lis=[]
for i in range(0,len(st)+1):
	for j in range(i+1,len(st)+1):
		lis.append(st[i:j])
	
l=set(lis)	
print((len(l)))
		
		


def cal(n):
	if n == 0 or n == 1:
		return 1
	return n*cal(n-1)

s = input()
dt = {}
for i in range(len(s)):
	for j in range(i,len(s)):
		#print s[i:j]
		if s[i:j+1] in dt :
			pass
		else:
			dt[s[i:j+1]] = 1

print(len(dt))


s = input();

n = len(s);
a= set();

for i in range (0,n+1):
	for j in range (i+1,n+1):
		a.add(s[i:j]);
		
print(len(a));		


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
s=input()
l=len(s)
sub=[]
for i in range(l):
	for j in range(i,l):
		sub.append(s[i:j+1])
			#print s[i:j]
print(len(set(sub)))
#print set(sub)


def ans(inp):
	s = tuple(inp)
	SubstringArray=[]
	for length in range(1, len(s)+1):
		for index in range(len(s)+1-length):
			SubstringArray.append(inp[index:index+length])
	return SubstringArray
x=input()
danger=set(ans(x))
print(len(danger))