Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Number of substrings in a string: n-squared or exponential

How many subtrings are there in a string in general?

Why does string x [1:n] have O(n^2) subtrings according to the lecture 21 Dynamic Programming III of        
6.006 from MIT? 
Why it is not O(2^n)?

Here is a link [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec21.pdf]

like image 570
zhushun0008 Avatar asked Jul 23 '14 03:07

zhushun0008


People also ask

How many substrings are in a string of length n?

Approach: The count of sub-strings of length n will always be len – n + 1 where len is the length of the given string.

How many substrings can be formed from a given string?

The total number of substrings formed by string of length N is (N*(N+1))/2, initialise count as (N*(N+1))/2.

How many substrings are in a string python?

Python String count()The count() method returns the number of occurrences of a substring in the given string.


1 Answers

Simply a substring is defined by two parameters [i,j] which are start index and end index for substring in the original string . Now 0<=i,j<=n as indices should be within the string, Total values i&j each can have are n so all combinations of [i,j] would be n*(n+1)/2 which is O(n^2)

like image 162
Vikram Bhat Avatar answered Sep 20 '22 08:09

Vikram Bhat