Determine if the string s=s1s2...sk

Assignment Help Basic Computer Science

Reference no: EM13166997

Suppose we want to determine if the string s=s1s2...sk is a substring much larger string a1a2...an. One approach is to compute h(s) with some hash function h. . Then, for each i = 1; 2,....,n-k+1 compute h(aiai+1...ai+k-1). If this value is identical to h(s), then compare this string with s, and return true if strings are identical. Otherwise proceed to next substring. Argue that the running time of this algorithm is O(kn). Prove that, if we assume the hash function is h(x0 ....x1)= E(l to i=0) xl-1 37^i. Then the running time can be reduced to O(n). Hint: argue that h(ai+1ai+2.... ai+k) can be computed in theta(1) steps assuming h(aiai+1...ai+k-1) has been computed.

Reference no: EM13166997

Questions Cloud

Produce a diagram showing schema : Produce a diagram showing schema and the partial and transitive dependencies in your 1NF. b. Produce a diagram showing table schema and any transitive dependencies in your 2NF

Write a java program that asks the user for his/her gender : According to researchers at Stanford Medical School, the ideal weight for a woman is found by multiplying her height in inches by 3.5 and subtracting 108.

Write an arm subroutine which will extract a substring : Write an ARM subroutine which will extract a substring from a string. You will need to use the library routine malloc to allocate memory for the new string. Use the pointers(a1,a2,a3) as stated below for writing ARM PROGRAM

Write a program that will read in 4 test scores per line : Write a program that will read in 4 test scores per line. Print the total number of points earned, your program should work for any number of lines of data.

Determine if the string s=s1s2...sk : Suppose we want to determine if the string s=s1s2...sk is a substring much larger string a1a2...an. One approach is to compute h(s) with some hash function h.

Derive the state equations : Derive the state equations A(t+1) and B(t+1) by substituting the input equations for the J and K variables, and draw the state diagram of the circuit.

Write a program that declares three one dimensional : Write a program that declares three one dimensional arrays named miles, gallons, and mpg . Each array should be declared in main( ) and should be capable of holding ten double

We base our need to implement composition upon : What criterion, or criteria, should be used to include objects of a class as data members of another class? In other words, what should we base our need to implement composition upon?

Write a program that stores the number : Write a program that stores the following numbers in the array named miles : 15, 22, 16, 18, 27, 23, 20. Use a pointer to copy the data stored in miles to another array named dist and then display the values in the dist array.

User Account

All Pages