分治算法

棋盘覆盖问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
(tr,tc)是棋盘左上角的方格坐标
(dr,dc)是特殊方格所在坐标
size是棋盘的行数和列数
*/
#include <iostream>
using namespace std;
#define N 1025
int board[N][N];
static int tile = 1;

void ChessBoard(int tr, int tc, int dr, int dc, int size) {
if(size == 1) return; //递归边界
int t = tile++; //L型骨牌号
int s = size/2; //分割棋盘
//覆盖左上角子棋盘
if(dr < tr + s && dc < tc + s)
ChessBoard(tr, tc, dr, dc, s);
else { //此棋盘中无特殊方格,用t号L型骨牌覆盖右下角
board[tr + s - 1][tc + s - 1] = t;
//覆盖其余方格
ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
}
//覆盖右上角子棋盘
if(dr < tr + s && dc >= tc + s)
Chessboard(tr, tc + s, dr, dc, s);
else {
board[tr + s - 1][tc + s] = t;
ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
}
//覆盖左下角子棋盘
if(dr >= tr + s && dc < tc + s) //特殊方格在此棋盘中
ChessBoard(tr + s, tc, dr, dc, s);
else { //此棋盘中无特殊方格,用t号L型骨牌覆盖右上角
board[tr + s][tc + s - 1] = t;
//覆盖其余方格
ChessBoard(tr + s, tc, tr + s, tc + s - 1, s);
}
//覆盖右下角子棋盘
if(dr >= tr + s && dc >= t c+ s) //特殊方格在此棋盘中
ChessBoard(tr + s, tc + s, dr, dc, s);
else { //此棋盘中无特殊方格,用t号L型骨牌覆盖左上角
board[tr + s][tc + s] = t;
//覆盖其余方格
ChessBoard(tr + s, tc + s, tr + s, tc + s, s);
}
}

int main() {
int i, j, k, x, y;
while(cin >> k) { //k cases
int size = 1 << k;
cin >> x >> y;
board[x][y] = 0;
ChessBoard(0, 0, x, y, size);
for(i = 0; i < size; i++) {
for(j = 0; j < size; j++)
cout << board[i][j] << '\t';
cout << '\n';
}
}
return 0;
}
1
2
3
4
n = 4^k
需(n-1)/3个L型骨牌填满
算法的时间复杂度: t(n)=4t(n/4)+c
Master Method求解得到: t(n)=Theta(n)

分治算法

归并排序

source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
// C++ program for Merge Sort
#include <iostream>
using namespace std;

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;

// Create temp arrays
int L[n1], R[n2];

// Copy data to temp arrays L[] and R[]
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

// Merge the temp arrays back into arr[l..r]

// Initial index of first subarray
int i = 0;

// Initial index of second subarray
int j = 0;

// Initial index of merged subarray
int k = l;

while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}

// Copy the remaining elements of
// L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

// Copy the remaining elements of
// R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
void mergeSort(int arr[],int l,int r){
if(l>=r){
return;//returns recursively
}
int m = (l+r-1)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}

// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
}

// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

cout << "Given array is \n";
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}

// This code is contributed by Mayank Tyagi

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
void QuickSort(T a[], int l, int r) {
if(l >= r) return;
int i = l, j = r + 1;
T pivot = a[l];
while(true) {
do { i++; } while(a[i] < pivot);
do { j--; } while(a[j] > pivot);
if(i >= j) break;
swap(a[i], a[j]);
}
a[l] = a[j];
a[j] = pivot;
QuickSort(a, l, j - 1);
QuickSort(a, j + 1, r);
}

寻找第 k 小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class T>
T select(T a[], int l, int r, int k) {
if(l >= r) return a[l];
int i = l, j = r + 1;
T pivot = a[l];
while(true) {
do { i++; } while(a[i] < pivot);
do { j--; } while(a[j] > pivot);
if(i >= j) break;
swap(a[i], a[j]);
}
if(j - i + 1 == k) return pivot;
a[l] = a[j];
a[j] = pivot;
if(j - i + 1 < k)
select(a, j + 1, r, k - j + l - 1);
else select(a, l, j - 1, k);
}

距离最接近的点对

source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

struct point {
double x;
double y;
point(double x, double y) : x(x), y(y) {}
point() { return; }
};

bool cmp_x(const point& A, const point& B) {
return A.x < B.x;
}

bool cmp_y(const point& A, const point& B) {
return A.y < B.y;
}

double distance(const point& A, const point& B) {
return sqrt(pow(A.x - B.x, 2) + pow(A.y - B.y, 2));
}

/*
* function: 合并,同第三区域最近点距离比较
* param: points 点的集合
* dis 左右两边集合的最近点距离
* mid x坐标排序后,点集合中中间点的索引值
*/
double merge(vector<point>& points, double dis, int mid) {
vector<point> left, right;
for(int i = 0; i < points.size(); i++) {
if(points[i].x - points[mid].x <= 0 && points[i].x - points[mid].x > -dis)
left.push_back(points[i]);
else if(points[i].x - points[mid].x > 0 && points[i].x - points[mid].x < dis)
right.push_back(points[i]);
}
sort(right.begin(), right.end(), cmp_y);
for(int i = 0, index; i < left.size(); i++) {
for(index = 0; index < right.size() && left[i].y < right[index].y; index++);
for(int j = 0; j < 7 && index + j < right.size(); j++) {
if(distance(left[i], right[j + index]) < dis)
dis = distance(left[i], right[j + index]);
}
}
return dis;
}

double closest(vector<point>& points) {
if(points.size() == 2) return distance(points[0], points[1]);
if(points.size() == 3) return min(distance(points[0], points[1]), min(distance(points[0], points[2]), distance(points[1], points[2])));
int mid = (points.size() >> 1) - 1;
double d1, d2, d;
vector<point> left(mid + 1), right(points.size() - mid - 1);
copy(points.begin(), points.begin() + mid + 1, left.begin()); //左边区域点集合
copy(points.begin() + mid + 1, points.end(), right.begin()); //右边区域点集合
d1 = closest(left);
d2 = closest(right);
d = min(d1, d2);
return merge(points, d, mid);
}

int main() {
int cnt;
printf("点个数:");
scanf("%d", &cnt);
vector<point> points;
double x, y;
for(int i = 0; i < cnt; i++) {
printf("第%d个点", i);
scanf("%lf%lf", &x, &y);
point p(x, y);
points.push_back(p);
}
sort(points.begin(), points.end(), cmp_x);
printf("最近点对值:%lf", closest(points));
return 0;
}

两个 n*n 的矩阵 A 与 B 的乘积是另一个 n*n 的矩阵 C,则:进行了 n^3 次乘法和 n^2(n-1) 次加法。

动态规划练习题

此文会不定期更新

购买股票问题

LeetCode714.买卖股票的最佳时机含手续费

给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8

  • 0 < prices.length <= 50000.
  • 0 < prices[i] < 50000.
  • 0 <= fee < 50000.

dp[i][0] 表示第 i 天未持有股票的最大利润,dp[i][1] 表示第 i天持有股票的最大利润。

那么对于 dp[i][0] ,它的来源有两种:第一种是在第 i - 1 天时手中就没有股票,到了第 i 天仍然没有;第二种是在第 i - 1 天手中有股票,到了第 i 天就卖出了。因此得到递推关系式:

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)

对于 dp[i][1] ,它的来源也有两种:第一种是在第 i - 1 天手中就有股票,第 i 天也没有抛售出去;第二种是在第 i - 1 天未持有股票,在第 i 天购入。递推关系式为:

dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

初始条件为:

dp[0][0] = 0 :第 0 天什么也没买

dp[0][1] = -prices[0] :第 0 天买了,那么就只可能买 prices[0] 的股票。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int dp[50010][2];
dp[0][0] = 0, dp[0][1] = -prices[0];
int n = prices.size();
for(int i = 0; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return max(dp[n - 1][0], dp[n - 1][1]);
}
};

LeetCode188.买卖股票的最佳时机

1
2
3
4
5
6
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {

}
}

回溯法

概念

回溯算法实际上是一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。

回溯法是一种选优搜索法,按选优条件向前搜索以达到目标。当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术称为回溯法,而满足回溯条件的某个状态的点称为回溯点。

许多复杂的、规模较大的问题都可以使用回溯法,有“通用解题方法”之称。

基本思想

在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根节点出发深度优先搜索解空间树。当探索到某一结点时,要先判断节点是否包含问题的解,如果包含,就从该节点出发继续探索下去,如果不包含,则逐层向其祖先节点回溯。

用回溯法求解问题的所有解时,要回溯到根,且根节点的所有可行的子树都要已被搜索遍才结束。

而若用回溯法求任意一个解时,只要搜索到问题的一个可行解就可以结束。

步骤

针对所给问题,确定问题的解空间:首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。

确定结点的扩展搜索规则

以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索

子集树:当所给问题是从 n 个元素的集合 S 中找出 S 满足的某种性质的子集时,相应的解空间树称为子集树。例如,0-1背包问题,要求在n个物品的集合S中,选出几个物品,使物品在背包容积C的限制下,总价值最大(即集合S的满足条件 <容积C下价值最大> 的某个子集)。

子集树是从集合S中选出符合限定条件的子集,故每个集合元素只需判断是否(0,1)入选,因此解空间应是一颗满二叉树。

1
2
3
4
5
6
7
8
9
10
void backtrack(int t) { //t是当前层数
if(t > n) output(x);
else {
for(int i = 0; i <= 1; i++) { //子集树是从集合S中,选出符合限定条件的子集,故每个元素判断是(1)否(0)选入即可(二叉树),因此i定义域为{0,1}
x[t] = i; //x[]表示是否加入点集,1表示是,0表示否
if(constraint(t) && bound(t)) //constraint(t)和bound(t)分别是约束条件和限定函数
backtrack(t + 1);
}
}
}

排列树:当问题是确定n个元素满足某种性质的排列时,相应的解空间称为排列树。排列树与子集树最大的区别在于,排列树的解包括整个集合S的元素,而子集树的解则只包括符合条件的集合S的子集。

1
2
3
4
5
6
7
8
9
10
11
void backtrack(int t) { //t是当前层数
if(t > n) output(x);
else {
for(int i = t; i <= n; i++) {
swap(x[t], x[i]);
if(constraint(t) && bound(t))
backtrack(t + 1);
swap(x[i], x[t]);
}
}
}

非子集树,非排列数

1
2
3
4
5
6
7
8
9
10
void backtrack(int t) {
if(t > n) output(x);
else {
for(int i = f(n, t); i <= g(n, t); i++) {
x[t] = h[i];
if(constraint(t) && bound(t))
backtrack(t + 1);
}
}
}

货箱装船问题

有两艘船,载重量为c1、c2,有n个货箱,重量分别为w1, w2, …, wn。

基本思路: 容易证明,如果一个给定装载问题有解,则采用下面的策略可得到最优装载方案。
(1)首先将第一艘轮船尽可能装满;
(2)将剩余的集装箱装上第二艘轮船。

将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集,使该子集中集装箱重量之和最接近c1。由此可知,装载问题等价于特殊的0-1背包问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n;       //货箱数目
int w[maxn]; //货箱重量数组
int c; //第1艘船的载重量
int cw; //当前装载的重量
int bestw; //目前最优装载的重量

void maxLoading(int i) { //从第i层节点搜索
if(i > n) {
if(cw > bestw) bestw = cw;
return;
}
if(cw + w[i] <= c) { //尝试x[i] = 1
cw += w[i];
maxLoading(i + 1);
cw -= w[i]; //回溯
}
maxLoading(i + 1); //尝试x[i] = 0
}

字符串哈希

什么是字符串哈希

字符串Hash可以通俗的理解为,把一个字符串转换为一个整数

如果我们通过某种方法,将字符串转换为一个整数,就可以便的确定某个字符串是否重复出现过,这是最简单的字符串Hash应用情景了。

当然也不难想到,如果有不同的两个字符串同时Hash到一个整数,这样就比较麻烦了。我们希望这个映射是一个单射,所以问题就是如何构造这个Hash函数,使得他们成为一个单射。

Hash方法

给定字符串 s,则 asc[s[i]] = s[i] - ‘a’ + 1.

自然溢出方法

1
2
unsigned long long Hash[n];
Hash[i] = Hash[i - 1] * p + asc[s[i]]

利用unsigned long long的范围自然溢出,相当于自动对 2^64 -1 取模。

单哈希方法

1
Hash[i] = (Hash[i - 1] * p + asc[s[i]]) % MOD

其中 p 和 MOD 均为质数,且有 p < MOD。

对于此种Hash方法,将 p 和 MOD 尽量取大即可,这种情况下,冲突的概率是很低的。

如取 p = 13, MOD = 101, 对字符串 “abc” 进行Hash。这里注意asc[s[i]]是s[i]的ascii码加1.

Hash[0] = 1;

Hash[1] = (Hash[0] * 13 + 2) % 101 = 15; // s[i] = ‘b’, asc[s[i]] = ‘b’ - ‘a’ + 1 = 2

Hash[2] = (Hash[1] * 13 + 3) % 101 = 97;

结果是Hash[n],即Hash[2]。所以此时认为 97 就是字符串”abc”的值。

双哈希方法

将一个字符串用不同的MOD Hash两次,将这两个结果用一个二元组表示,作为Hash结果。

1
2
Hash1[i] = (Hash[i - 1] * p + asc[s[i]]) % MOD1;
Hash2[i] = (Hash[i - 1] * p + asc[s[i]]) % MOD2;

Hash的结果为 < Hash1[n], Hash2[n] >

这种Hash很安全。

求子串公式

假设有一个∣S∣=5 的字符串,设 Si 为第 i 个字符,其中 1 ≤ i ≤ 5。

根据定义分别求出hash[i]:

hash[1] = s1;

hash[2] = s1 ∗ p + s2;

hash[3] = s1 ∗ p^2 + s2 ∗ p + s3;

hash[4] = s1 ∗ p^3 + s2 ∗ p^2 + s3 ∗ p + s4;

hash[5] = s1 ∗ p^4 + s2 ∗ p^3 + s3 ∗ p^2 + s4 ∗ p + s5;

现在要求子串 s3s4 的hash值,不难得出为s3 ∗ p + s4。
Hash[4] - Hash[2] * pow(p, 4 - 3 + 1)

所以公式如下:

Hash[l~r] = Hash[r] - Hash[l - 1] * pow(p, r - l + 1)

考虑到取模:

Hash[l~r] = ((Hash[r] - Hash[l - 1] * pow(p, r - l + 1)) % MOD + MOD) % MOD

应用

POJ2774

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define maxn 100010
#define p 131
// #define INF 0x3f3f3f3f
// #define MOD 1000000007

// Hash1和Hash2存储两个字符串的哈希值,
// po记录p的乘方(相当于转化为p进制),tmp用于比较(后面会讲解)
ull Hash1[maxn], Hash2[maxn], po[maxn], tmp[maxn];
int len1, len2; // 两字符串的长度
char s1[maxn], s2[maxn];

// 求h的子串s[l~r](包括s[l]和s[r])的Hash值
ull getHash(ull* h, int l, int r) {
return h[r] - h[l - 1] * po[r - l + 1];
}

/*
check函数用来判断是否有长度为len的相同子串
先将Hash1的长度为len的子串的Hash值依次求出,存入tmp数组中
将tmp由小到大排序(这里排序只是为了便于Hash2的二分查找)
因为二分查找要求数组有序!
*/
bool check(int len) {
int cnt = 0;
for(int i = 1; i + len - 1 <= len1; i++)
tmp[cnt ++] = getHash(Hash1, i, i + len - 1);
sort(tmp, tmp + cnt);
for(int i = 1; i + len - 1 <= len2; i++) {
ull x = getHash(Hash2, i, i + len - 1);
if(binary_search(tmp, tmp + cnt, x)) return true;
// 这里用到了<algorithm>中的binary_search函数,这是一个bool类型函数,
// 是在[tmp, tmp + cnt),即[tmp, tmp + cnt - 1]范围内
// 二分查找x,如果找到了就返回true,否则返回false
}
return false;
}

void init_po() { // 将p的乘方都算出来,打表
po[0] = 1;
for(int i = 1; i < maxn; i++)
po[i] = po[i - 1] * p;
}

int main() {
init_po();
while(~scanf("%s%s", s1 + 1, s2 + 1)) { // s1和s2都从索引1开始存储
len1 = strlen(s1 + 1);
len2 = strlen(s2 + 1);

// 计算s1和s2的Hash值
Hash1[0] = Hash2[0] = 0;
for(int i = 1; i <= len1; i++)
Hash1[i] = Hash1[i - 1] * p + (s1[i] - 'a');
for(int i = 1; i <= len2; i++)
Hash2[i] = Hash2[i - 1] * p + (s2[i] - 'a');

// 二分查找最大长度
int l = 0, r = min(len1, len2);
int ans = 0;
while(l <= r) {
int m = (l + r) >> 1; // 移位更快
if(check(m)) { // 如果m满足长度为m的子串相等
l = m + 1; // 就增大左边界l,看看有没有更大的长度
ans = m; // ans更新为当前的最大值
}
else
r = m - 1; // 没有找到,那就先减小右边界看看有没有符合的m
}
printf("%d\n", ans);
}
return 0;
}

最大公共子序列和最大公共子串

最大公共子序列

最大公共子串

动态规划(未优化)

动态规划(一级空间优化)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

char s1[1000001], s2[1000001];
int dp[2][1000005];

int lcs() {
int len1 = strlen(s1), len2 = strlen(s2);
int i, j, cur = 1, pre = 0, cnt = 0;
if(len2 > len1) {
for(i = 0; i <= len2; i++) dp[0][i] = 0;
dp[1][0] = 0;
for(i = 1; i <= len1; i++) {
for(j = 1; j <= len2; j++) {
if(s1[i - 1] == s2[j - 1]) {
dp[cur][j] = dp[pre][j - 1] + 1;
cnt = max(cnt, dp[cur][j]);
}
else dp[cur][j] = 0;
}
swap(cur, pre);
}
return cnt;
}
else {
for(i = 0; i <= len1; i++) dp[0][i] = 0;
dp[1][0] = 0;
for(i = 1; i <= len2; i++) {
for(j = 1; j <= len1; j++) {
if(s2[i - 1] == s1[j - 1]) {
dp[cur][j] = dp[pre][j - 1] + 1;
cnt = max(cnt, dp[cur][j]);
}
else dp[cur][j] = 0;
}
swap(cur, pre);
}
return cnt;
}
}

int main() {
while(~scanf("%s%s", s1, s2)) {
int ans = lcs();
printf("%d\n", ans);
}
return 0;
}

动态规划(二级空间优化)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

char s1[1000001], s2[1000001];
int dp[1000001];

int lcs() {
int len1 = strlen(s1), len2 = strlen(s2);
int i, j, tmp, old, cnt = 0;
if(len2 > len1) {
for(i = 0; i <= len2; i++) dp[i] = 0;
for(i = 1; i <= len1; i++) {
old = dp[0];
for(j = 1; j <= len2; j++) {
tmp = dp[j];
if(s1[i - 1] == s2[j - 1]) {
dp[j] = old + 1;
cnt = max(cnt, dp[j]);
}
else dp[j] = 0;
old = tmp;
}
}
return cnt;
}
else {
for(i = 0; i <= len1; i++) dp[i] = 0;
for(i = 1; i <= len2; i++) {
old = dp[0];
for(j = 1; j <= len1; j++) {
tmp = dp[j];
if(s2[i - 1] == s1[j - 1]) {
dp[j] = old + 1;
cnt = max(cnt, dp[j]);
}
else dp[j] = 0;
old = tmp;
}
}
return cnt;
}
}

int main() {
while(~scanf("%s%s", s1, s2)) {
int ans = lcs();
printf("%d\n", ans);
}
return 0;
}

后缀数组

桶排序

对于待排序的数组a,在排序时逐个遍历数组a,将数组a的值作为”桶数组r”的下标。当a中数据被读取时,就将桶的值加1。例如,读取到数组a[3]=5,则将r[5]的值+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
void bucket_sort(int a[], int n) {
int i, j;
int bucket[maxn]; // maxn是a[]的最大值
memset(bucket, 0, sizeof(bucket));
// 计数
for(i = 0; i < n; i++)
bucket[a[i]]++;
// 排序
for(i = 0, j = 0; i < maxn; i++) {
while((bucket[i]--) > 0)
a[j++] = i;
}
}

基数排序

桶排序的扩展。它的基本思想是:将整数按位数切割成不同的数字,然后按每个位数分别比较。
具体做法是:将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int base(int i) {
if(i == 0) return 10;
else return 10 * base(i - 1);
}

void bucket_sort(int bit) {
int bucket[maxn];
int tmp[n];
memset(bucket, 0, sizeof(bucket));
for(int i = 0; i < n; i++)
bucket[(a[i] / base(bit)) % 10]++;
for(int i = 1; i < maxn; i++)
bucket[i] += bucket[i - 1];
for(int i = n - 1; i >= 0; i--) {
tmp[bucket[(a[i] / base(bit)) % 10] - 1] = a[i];
bucket[(a[i] / base(bit)) % 10]--;
}
for(int i = 0; i < n; i++)
a[i] = tmp[i];
}

void radix_sort() {
int bit = getbit(); //获取数组a的位数
for(int i = 0; i < bit; i++)
bucket_sort(i);
print(); //已排好序
}

后缀数组

1
2
3
4
Str: 需要处理的字符串(长度为Len)
Suffix[i]: Str下标为i~Len的连续子串(例如Str="abcdef", Suffix[3]="def")
Rank[i]: Suffix[i]在所有后缀中的排名
SA[i]: 排名为i的后缀的起始下标,即排名为i的后缀为Suffix[SA[i]],与Rank是互逆运算

后缀数组指的就是这个SA[i],有了它,我们就可以实现一些很强大的功能(如不相同子串个数、连续重复子串等)。如何快速的到它,便成为了这个算法的关键。而SARank是互逆的,只要求出任意一个,另一个就可以O(Len)得到。
现在比较主流的算法有两种,倍增DC3,在这里,就主要讲一下稍微慢一些,但比较好实现以及理解的倍增算法(虽说慢,但也是O(Len logLen))的。

倍增算法

Height数组

1
2
Height[i]: 表示Suffix[SA[i]]和Suffix[SA[i-1]]的最长公共前缀,也就是排名相邻的两个后缀的最长公共前缀
H[i]: 等于Height[Rank[i]],即Height[i]=H[SA[i]]

H[i] >= H[i-1] - 1

证明:设Suffix[k]是排在Suffix[i - 1]前一名的后缀,则它们的最长公共前缀是H[i - 1]。都去掉第一个字符,就变成Suffix[k + 1]Suffix[i]如果H[i - 1] = 0或1,那么H[i] ≥ 0显然成立。否则H[i] ≥ H[i - 1] - 1(去掉了原来的第一个,其他前缀一样相等),所以Suffix[i]和在它前一名的后缀的最长公共前缀至少是H[i - 1] - 1。

random_shuffle原理

random_shuffle,即随机洗牌,算法描述如下:

P1.初始化:

P2.生成U:

P3.交换:

P4.减小j:

数学原理其实很简单。第一个被选中的数,概率是1/t,第二个被选中的数的概率是1/(t-1) * (t-1)/t = 1/t,…

这是因为第二个数第一次未被选中,所以是(t-1)/t,而第一次选完之后还剩下t-1个数,所以是1/(t-1),相乘即可。

于是可以看出,每个数被选到的概率是一样的。

Java代码如下:

1
2
3
4
5
6
7
8
9
10
for(int i = 0; i < arr.length; i++){
for(int j = 0; j < arr[i].length; j++){
int i1 = (int)(Math.random() * arr.length);
int j1 = (int)(Math.random() * arr[i].length);

int temp = arr[i][j];
arr[i][j] = arr[i1][j1];
arr[i1][j1] = temp;
}
}

PS:很早就知道了随机洗牌是等概率的,而且有时也会用到这个函数,就是忘了具体算法是什么。在网上找了很久都没有找到想要看的东西,最后无意中发现有人说《计算机程序设计艺术》第二卷有它的解释,于是赶紧看了看。概率是我自己推的,的确很简单。在此记录一下。