模板
核心思想：将字符串看成P进制数，P的经验值是
131或
13331，取这两个值的冲突概率低
小技巧：取模的数用
2^64，这样直接用
unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL
;
ULL h
[N
], p
[N
];
p
[0] = 1;
for (int i
= 1; i
<= n
; i
++ )
{
h
[i
] = h
[i
- 1] * P
+ str
[i
];
p
[i
] = p
[i
- 1] * P
;
}
ULL
get(int l
, int r
)
{
return h
[r
] - h
[l
- 1] * p
[r
- l
+ 1];
}
兔子与兔子
题目描述
很久很久以前，森林里住着一群兔子。 有一天，兔子们想要研究自己的 DNA 序列。 我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母）。 然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。 注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。 输入格式 第一行输入一个 DNA 字符串 S。 第二行一个数字 m，表示 m 次询问。 接下来 m 行，每行四个数字 l1,r1,l2,r2，分别表示此次询问的两个区间，注意字符串的位置从1开始编号。 输出格式 对于每次询问，输出一行表示结果。 如果两只兔子完全相同输出 Yes，否则输出 No（注意大小写）。 数据范围 1≤length(S),m≤1000000 输入样例： aabbaabb 3 1 3 5 7 1 3 6 8 1 2 1 2 输出样例： Yes No Yes
题解
模板题，套用上面的模板即可
代码
#include <iostream>
#include <cstring>
using namespace std
;
typedef unsigned long long ULL
;
const int N
= 1000010, base
= 131;
int h
[N
], p
[N
];
char str
[N
];
int get(int l
, int r
)
{
return h
[r
] - h
[l
- 1] * p
[r
- l
+ 1];
}
int main()
{
scanf("%s", str
+ 1);
int n
= strlen(str
+ 1);
p
[0] = 1;
for(int i
= 1; i
<= n
; i
++)
{
h
[i
] = h
[i
- 1] * base
+ str
[i
] - 'a' + 1;
p
[i
] = p
[i
- 1] * base
;
}
int m
;
scanf("%d", &m
);
while(m
--)
{
int l1
, r1
, l2
, r2
;
scanf("%d%d%d%d" , &l1
, &r1
, &l2
, &r2
);
if(get(l1
, r1
) == get(l2
, r2
)) puts("Yes");
else puts("No");
}
return 0;
}
回文子串的最大长度
题目描述
如果一个字符串正着读和倒着读是一样的，则称它是回文的。 给定一个长度为N的字符串S，求他的最长回文子串的长度是多少。 输入格式 输入将包含最多30个测试用例，每个测试用例占一行，以最多1000000个小写字符的形式给出。 输入以一个以字符串“END”（不包括引号）开头的行表示输入终止。 输出格式 对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。 每个输出占一行。 输入样例： abcbabcbabcba abacacbaaaab END 输出样例： Case 1: 13 Case 2: 6
题解
套用字符串哈希算法。算出正序，逆序哈希。枚举中点，然后二分半径。技巧：在字符之间插入一个#，这样字符串长度就变成了偶数，但要注意的是：算原来字符长度的时候 要判断第一个字符是什么，如果不是#，这样字符长度就是半径+1，否则就是半径。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std
;
typedef unsigned long long ULL
;
const int N
= 2000010, base
= 131;
char str
[N
];
ULL hl
[N
], hr
[N
], p
[N
];
ULL
get(ULL h
[], int l
, int r
)
{
return h
[r
] - h
[l
- 1] * p
[r
- l
+ 1];
}
int main()
{
int T
= 1;
while(scanf("%s", str
+ 1), strcmp(str
+ 1, "END"))
{
int n
= strlen(str
+ 1);
for(int i
= 2 * n
; i
; i
-= 2)
{
str
[i
] = str
[i
/ 2];
str
[i
- 1] = 'a' + 26;
}
n
= n
* 2;
p
[0] = 1;
for(int i
= 1, j
= n
; i
<= n
; i
++, j
--)
{
hl
[i
] = hl
[i
- 1] * base
+ str
[i
] -'a' + 1;
hr
[i
] = hr
[i
- 1] * base
+ str
[j
] -'a' + 1;
p
[i
] = p
[i
- 1] * base
;
}
int res
= 0;
for(int i
= 1; i
<= n
; i
++)
{
int l
= 0, r
= min(i
- 1, n
- i
);
while(l
< r
)
{
int mid
= l
+ r
+ 1 >> 1;
if(get(hl
, i
- mid
, i
- 1) != get(hr
, n
- (i
+ mid
) + 1, n
- (i
+ 1) + 1)) r
= mid
- 1;
else l
= mid
;
}
if(str
[i
- l
] <= 'z') res
= max(res
, l
+ 1);
else res
= max(res
, l
);
}
printf("Case %d: %d\n", T
++, res
);
}
return 0;
}
后缀数组
题目描述
后缀数组 (SA) 是一种重要的数据结构，通常使用倍增或者DC3算法实现，这超出了我们的讨论范围。 在本题中，我们希望使用快排、Hash与二分实现一个简单的O(nlog2n)的后缀数组求法。 详细地说，给定一个长度为 n 的字符串S（下标 0~n-1），我们可以用整数 k(0≤k<n) 表示字符串S的后缀 S(k~n-1)。 把字符串S的所有后缀按照字典序排列，排名为 i 的后缀记为 SA[i]。 额外地，我们考虑排名为 i 的后缀与排名为 i-1 的后缀，把二者的最长公共前缀的长度记为 Height[i]。 我们的任务就是求出SA与Height这两个数组。 输入格式 输入一个字符串，其长度不超过30万。 字符串由小写字母构成。 输出格式 第一行为数组SA，相邻两个整数用1个空格隔开。 第二行为数组Height，相邻两个整数用1个空格隔开，我们规定Height[1]=0。 输入样例： ponoiiipoi 输出样例： 9 4 5 6 2 8 3 1 7 0 0 1 2 1 0 0 2 1 0 2
题解
先想出朴素做法：用一个下标表示字符串后缀的开头。然后使用快排对这些后缀排序。 比较函数：挨个字符比较。求两个字符串的最长公共前缀长度，可以用字符串哈希的做法。即二分枚举最大长度，如何判断 这两个字符串是相同的呢？可以求出在这个长度下的字符串哈希值，通过比较哈希值，判断在这两个字符串是不是相同的字符串。优化比较函数：可以先求出两个后缀的最大公共长度，然后比较最大公共长度后一个字符的大小即可。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
using namespace std
;
typedef unsigned long long ULL
;
const int N
= 300010, base
= 131;
char str
[N
];
int sa
[N
];
ULL h
[N
], p
[N
];
int n
;
ULL
get(int l
, int r
)
{
return h
[r
] - h
[l
- 1] * p
[r
- l
+ 1];
}
int get_max_common_prefix(int a
, int b
)
{
int l
= 0, r
= min(n
- a
+ 1, n
- b
+ 1);
while(l
< r
)
{
int mid
= l
+ r
+ 1>> 1;
if(get(a
, a
+ mid
- 1) != get(b
, b
+ mid
- 1)) r
= mid
- 1;
else l
= mid
;
}
return l
;
}
bool cmp(int a
, int b
)
{
int l
= get_max_common_prefix(a
, b
);
int av
= str
[a
+ l
];
int bv
= str
[b
+ l
];
return av
< bv
;
}
int main()
{
scanf("%s", str
+ 1);
n
= strlen(str
+ 1);
p
[0] = 1;
for(int i
= 1; i
<= n
; i
++)
{
h
[i
] = h
[i
- 1] * base
+ str
[i
] - 'a' + 1;
p
[i
] = p
[i
- 1] * base
;
sa
[i
] = i
;
}
sort(sa
+ 1, sa
+ n
+ 1, cmp
);
for(int i
= 1; i
<= n
; i
++) printf("%d ", sa
[i
] - 1);
puts("");
for(int i
= 1; i
<= n
; i
++)
{
if(i
== 1) printf("0 ");
else printf("%d ", get_max_common_prefix(sa
[i
- 1], sa
[i
]));
}
puts(" ");
return 0;
}
