写在前面：
用printf输出一个浮点数用f而不用lf
洛谷P1659 [国家集训队]拉拉队排练：
求出奇数长度的回文串，加入以i为中心的回文串长度为5，那么它还包含长度为3的，长度为1的，可以求一个后缀和，用快速幂加速
难度：3
- 字符串哈希
①自然溢出（unsigned long long）
②单哈希（用大质数）
③双哈希
难度：2
- HDU 4622 Reincarnation
求区间不相同子串个数
用哈希的方法：
区间哈希求法：
for (int L = 1; L <= len; L++)
{
for (int i = 1; i + L - 1 <= len; i++)
{
a[i][i+L-1] = hah[i + L - 1] - hah[i - 1] * Pow[L];
}
}
把哈希值相同的挂一个链表上，存一下序列位置且能保证链表尾递增，具体看代码
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
#define re register int
#define ull unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
#define N 3009
#define lson rt << 1
#define rson rt << 1 | 1
#define ne e[i].to
#define mo 998244353
#define lowbit(x) (x) & (-(x))
inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ll)(ch - '0');
ch = getchar();
}
return x * f;
}
ull Pow[N], hah[N];
int head[10010], cnt, T, ans[2020][2020];
char st[2020];
struct node
{
ull nex, val, id, pre;
} e[N];
int insert(ull val, int id)
{
int u = val % 10007;
for (int i = head[u]; i; i = e[i].nex)
{
if (val == e[i].val)
{
int tmp = e[i].pre;
e[i].pre = id;
return tmp;
}
}
e[++cnt].nex = head[u];
head[u] = cnt;
e[cnt].pre = id;
e[cnt].val = val;
return 0;
}
int main()
{
Pow[0] = 1;
for (int i = 1; i <= 3000; i++)
Pow[i] = Pow[i - 1] * 131;
int T = read();
while (T--)
{
scanf("%s", st);
int len = strlen(st);
for (int i = 1; i <= len; i++)
hah[i] = hah[i - 1] * 131 + st[i - 1] - 'a';
memset(ans, 0, sizeof(ans));
for (int L = 1; L <= len; L++)
{
memset(head, 0, sizeof(head));
cnt = 0;
for (int i = 1; i + L - 1 <= len; i++)
{
int tmp = insert(hah[i + L - 1] - hah[i - 1] * Pow[L], i);
ans[i][i + L - 1]++;
ans[tmp][i + L - 1]--;
}
}
for (int i = len; i >= 0; i--)
for (int j = i; j <= len; j++)
ans[i][j] += ans[i + 1][j] + ans[i][j - 1] - ans[i + 1][j - 1];
int Q = read();
while (Q--)
{
int l = read(), r = read();
printf("%d
", ans[l][r]);
}
}
return 0;
}
难度：3
- P4503 [CTSC2014]企鹅QQ
①.预处理，算出前i段的哈希值（这里使用的为进制哈希）
②.枚举不同位是哪一位，
求所有字符串在去掉这一位后的哈希值，
用排序等方法统计相同的对数。
设去掉的是第k位置的哈希值:
x = hs[i - 1] * p[len - i] + hs[len] - hs[i] * p[len - i]
难度：3
- HDU2896
AC自动机，只要用堆或者其他什么的东西记录一下匹配到的编号，然后排序就行，建议用stl库里的堆处理
难度：3
- KMP模板
KMP都看了好久QAQ，太菜了
#include<bits/stdc++.h>
#define ll long long
#define inf 0x7fffff
#define N 1000010
#define lson rt<<1
#define rson rt<<1|1
#define mo 998244353
using namespace std;
ll read()
{
ll x=0;int f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int nex[N],lena,lenb;
char s1[N],s2[N];
void getnex()
{
int j=0;
for (int i=1;i<lenb;i++)
{
while (j&&s2[i]!=s2[j]) j=nex[j];
j+=s2[i]==s2[j]?1:0;
nex[i+1]=j;
}
}
int main()
{
scanf("%s%s",s1,s2);
lena=strlen(s1),lenb=strlen(s2);
getnex();
int j=0;
for (int i=0;i<lena;i++)
{
while (j&&s1[i]!=s2[j]) j=nex[j];
j+=s1[i]==s2[j]?1:0;
if (j==lenb) printf("%d
",i-lenb+2);
}
for (int i=1;i<=lenb;i++) printf("%d ",nex[i]);
return 0;
}
难度：2