1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
mote1985 [20]
3 years ago
12

A shuffle of two strings X and Y is formed by interspersing the characters into a new string, keeping the characters of X and Y

in the same order. For example, the string BANANA ANANAS is a shue of the strings BANANA and ANANAS in several different ways.
BANANAANANAS BANANAANANAS BANANANANA

Similarly, the strings PRODGYRNAMAMMIINCG and DYPRONGARMAMMICING are both shuffles of DYNAMIC and PROGRAMMING:

PROGRAMMING PROGRAMMING

Describe and analyze an efficient algorithm to determine, given throe strings A1 [1...m], B [1...n] and C[1...m+n], whether C is a shuffle of A and B.
Computers and Technology
1 answer:
levacccp [35]3 years ago
3 0

Shuffle (A[1..m], B[1..n], C[1..m+n]):

Shuf[0, 0] ← True

for j ← 1 to n

Shuf[0, j] ← Shuf[0, j − 1] ∧ (B[j] = C[j])

for i ← 1 to n

Shuf[i, 0] ← Shuf[i − 1, 0] ∧ (A[i] = B[i])

for j ← 1 to n

Shuf[i, j] ← False

if A[i] = C[i + j]

Shuf[i, j] ← Shuf[i, j] ∨ Shuf[i − 1, j]

if B[i] = C[i + j]

Shuf[i, j] ← Shuf[i, j] ∨ Shuf[i, j − 1]

return Shuf[m, n]

The algorithm runs in O(mn) time.

You might be interested in
Why is color important for all objects drawn ?​
Sati [7]
Technically, drawing in colored pencil is simply layering semitransparent colors on paper to create vivid paintings. Every color has three qualities
7 0
2 years ago
An administrative assistant types a document, saves, and prints. The assistant is using _____.
9966 [12]
The answer to your question is software. 
3 0
2 years ago
3) How ash traditional technology and modern
Fynjy0 [20]

Answer:

While the developed world benefits from the modern explosion of technology, countries like Ethiopia continue to rely on their forefathers' methods for important daily tasks such as farming, cooling, and providing clean water. These activities are often physically challenging, time and energy intensive, and are often carried out by female family members in many such societies. Furthermore, they can damage the local ecology and climate, such as deforestation and soil erosion caused by the use of trees for firewood. Western technologies are often too complicated, expensive, unacceptable, and difficult to maintain in developing societies, so they are of little or no use in these situations.

4 0
2 years ago
Which type of network treats all processors equally, and allows peripheral devices to be shared without going to a separate serv
Elis [28]
The correct answer is P2P or peer-to-peer servers.

Hope I helped ;)
7 0
2 years ago
Which of the following office online apps is most effective for creating multi media presentation
Brrunno [24]
Google slides is the best out there
3 0
3 years ago
Read 2 more answers
Other questions:
  • Write the interface (.h file) of a class ContestResult containing: An data member winner of type string, initialized to the empt
    14·1 answer
  • 9. Name at least two types of hard drives?
    6·1 answer
  • what is it called when someone uses software to run multiple operating systems on one computer at the same time? A.functional vi
    9·1 answer
  • Which of the following statements is true with regards to satellite Internet access?
    13·2 answers
  • Refer to the color wheel to identify the color scheme.
    13·1 answer
  • Select one or more of the following: Which of these events will cause signal(s) to be generated by the kernel (the operating sys
    6·1 answer
  • X = 1 if (A = 1 OR B = 1) OR (A = 0 AND B = 1
    7·1 answer
  • My game is telling me to "Press any key." Where is the "any" key?????
    13·1 answer
  • python. create a program that asks the user to input their first name and their favorite number. Then the program should output
    12·1 answer
  • What is the purpose of memory address?​
    9·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!