# 字符串匹配的后缀算法

const char* strstr( const char* str, const char* target );
char* strstr( char* str, const char* target );

Finds the first occurrence of the byte string target in the byte string pointed to by str. The terminating null characters are not compared.

# SRM657 DIV1 Problem Sets

Cat Snuke came up with some problems. He wants to construct as many problem sets as possible using those problems. Each problem set must contain exactly three problems: one for the Easy slot, one for the Medium slot, and one for the Hard slot. Each problem can only be assigned to a single slot in a single problem set. He came up with E + EM + M + MH + H problems in total. The distribution of the problems is as follows:

• E problems can only be used in the Easy slot.
• EM problems can be used either in the Easy slot or the Medium slot.
• M problems can only be used in the Medium slot.
• MH problems can be used either in the Medium slot or the Hard slot.
• H problems can only be used in the Hard slot.

Return the maximal number of problem sets he can construct.

# SRM656 DIV1 Random Pancake Stack

Charlie has N pancakes. He wants to serve some of them for breakfast. We will number the pancakes 0 through N-1. For each i, pancake i has width i+1 and deliciousness d[i].

Charlie chooses the pancakes he is going to serve using the following randomized process: He starts by choosing the first pancake uniformly at random from all the pancakes he has. He places the chosen pancake onto a plate. This pancake now forms the bottom of a future stack of pancakes. Then, Charlie repeats the following procedure:

1. If there are no more pancakes remaining, terminate.
2. Choose a pancake uniformly at random from the pancakes that have not been chosen yet.
3. If the width of this pancake is greater than the width of the pancake on top of the stack, terminate without taking it.
4. Place the chosen pancake on top of the stack and go back to step 1.

You are given the vector d with N elements. The total deliciousness of a serving of pancakes is the sum of the deliciousness of all pancakes used in the serving. Compute and return the expected value of the total deliciousness of the pancakes chosen by Charlie.

# 全局最小割：Karger’s Min Cut Algorithm

Cut in an undirected graph

Can we do better?

# Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

# Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

# Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?