Hash哈希
𝑠=“123abc”, 𝑏=97
𝐻𝑎𝑠ℎ(𝑠)=（1∗97^5+2∗97^4+3∗97^3+𝑎∗97^2+（ASCII）𝑏∗97^1+𝑐 ）𝑚𝑜𝑑 𝑚
它的作用在于把一个字符串转化为一个数字。
映射：string ——> int
base与m互质，则发生哈希碰撞概率减小
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
|
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int base=131;
ull a[10010];
char st[10010];
int ans=1;
inline void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>st;
int len=strlen(st);
ull cnt=0;
for(int j=0;j<len;j++)
{
cnt=cnt*base+st[j];
}
a[i]=cnt;
}
sort(a+1,a+n+1);
for(int i=1;i<n;i++)
{
if(a[i]!=a[i+1]) ans++;
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
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
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int base=131;
inline void solve()
{
int n;
cin>>n;
string st;
cin>>st;
st=" "+st;
vector<int> hasa(n+1),hasb(n+1),q(n+1,1);
for(int i=1;i<=n;++i)
{
hasa[i]=hasa[i-1]*base+(st[i]=='1');
hasb[i]=hasb[i-1]*base+(st[n-i+1]=='0');
q[i]=q[i-1]*base;
}
int ans=0;
auto get=[&](vector<int> &hash,int l,int r)
{
return hash[r]-hash[l-1]*q[r-l+1];
};
auto chk=[&](int l,int r)->bool
{
return get(hasa,l,r)==get(hasb,n-r+1,n-l+1);
};
auto find=[&](int i)->int
{
int l=0,r=min(i,n-i);
while(l<r)
{
int mid=l+r+1>>1;
if(chk(i-mid+1,i+mid)) l=mid;
else r=mid-1;
}
return l;
};
for(int i=1;i<n;++i)
{
ans+=find(i);
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
|
tips
C++ lambda函数总结
[&] ————> lamda函数/匿名函数
[&]—按引用访问所有动态变量
[=]/[]—按值访问所有动态变量
KMP
KMP问题
该算法由 Knuth、Pratt 和 Morris 在 1977 年共同发布
时间复杂度O(m+n) 内存O(n)
给定一个文本 t 和一个字符串 s，我们尝试找到并展示 s 在 t 中的所有出现（occurrence）。
按照nxt边建一棵树。在match过程中，当前结点的所有祖先的所有前缀，都被匹配到。
p3375
给出两个字符串 s1 和 s2，若 s1 的区间 [l,r] 子串与 s2 完全相同,则称 s2 在 s1 中出现了，其出现位置为 l。现在请你求出 s2 在 s1 中所有出现的位置。
定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。
对于 s2，你还需要求出对于其每个前缀 s′ 的最长 border t’ 的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def kmp_search(string,patt):
next=build_next(patt)
i=0 //主串中的指针
j=0 //子串中的指针
while i<len(string):
if string[i]==patt[j]: //字符匹配，指针后移
i+=1
j+=1
elif j>0; //字符失配，根据next跳过子串前面的一些字符
j=next[j-1]
else: //子串第一个字符失配
i+=1
if j==len(patt): //匹配成功
return i=j
|
next数组本质：寻找子串中“相同前后缀的长度”，并且一定是最长的前后缀
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
|
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000010
int kmp[MAXN];
int lena,lenb,j;
char a[MAXN],b[MAXN];
int main()
{
cin>>a+1;
cin>>b+1;
lena=strlen(a+1);
lenb=strlen(b+1);
for (int i=2;i<=lenb;i++)
{
while(j&&b[i]!=b[j+1])
{
j=kmp[j];
}
if(b[j+1]==b[i]) j++;
kmp[i]=j;
}
j=0;
for(int i=1;i<=lena;i++)
{
while(j>0 && b[j+1]!=a[i])
{
j=kmp[j];
}
if (b[j+1]==a[i]) j++;
if (j==lenb)
{
cout<<i-lenb+1<<endl;
j=kmp[j];
}
}
for (int i=1;i<=lenb;i++)
{
cout<<kmp[i]<<" ";
}
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
|
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000010
int kmp[MAXN];
int lena,lenb,j;
string a,b;
int main()
{
cin>>a;
cin>>b;
a=" "+a;
b=" "+b;
lena=a.size()-1;
lenb=b.size()-1;
for (int i=2;i<=lenb;i++)
{
while(j&&b[i]!=b[j+1]) j=kmp[j];
if(b[j+1]==b[i]) j++;
kmp[i]=j;
}
j=0;
for(int i=1;i<=lena;i++)
{
while(j>0 && b[j+1]!=a[i])
{
j=kmp[j];
}
if (b[j+1]==a[i]) j++;
if (j==lenb)
{
cout<<i-lenb+1<<endl;
j=kmp[j];
}
}
for (int i=1;i<=lenb;i++)
{
cout<<kmp[i]<<" ";
}
return 0;
}
|
字典树
Trie树
Trie 树，即字典树，是一种树形结构。典型应用是用于统计和排序大量的字符串前缀来减少查询时间，最大限度地减少无谓的字符串比较。
Trie 树的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
上图是一棵Trie树，表示了关键字集合{“a”，”to”，”tea”，”ted”，”ten”，”in”.”inn”}。从上图可以纳出Trie树的基本性质:
1 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
2 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3 每个节点的所有子节点包含的字符互不相同。
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
|
#include <bits/stdc++.h>
using namespace std;
int T,q,n,t[3000005][65],cnt[3000005],idx;
string s;
int getnum(char x)
{
if(x>='A'&&x<='Z') return x-'A';
else if(x>='a'&&x<='z') return x-'a'+26;
else return x-'0'+52;
}
void insert(string s)
{
int p=0,len=s.size();
for(int i=0;i<len;i++)
{
int c=getnum(s[i]);
if(!t[p][c]) t[p][c]=++idx;
p=t[p][c];
cnt[p]++;
}
}
int find(string s)
{
int p=0,len=s.size();
for(int i=0;i<len;i++)
{
int c=getnum(s[i]);
if(!t[p][c]) return 0;
p=t[p][c];
}
return cnt[p];
}
int main()
{
cin>>T;
while(T--)
{
for(int i=0;i<=idx;i++)
{
for(int j=0;j<=122;j++)
{
t[i][j]=0;
}
}
for(int i=0;i<=idx;i++)
{
cnt[i]=0;
}
idx=0;
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>s;
insert(s);
}
for(int i=1;i<=q;i++)
{
cin>>s;
cout<<find(s)<<endl;
}
}
return 0;
}
|
Manacher
——Glenn K. Manacher
szu-acm
oi-wiki
已知一回文子串LMR
…..L…k….M….i…R…..
i>R p[i]=1,暴力向两边扩展
i<=R 找到i关于M对称点k
若p[2M-i]<R-i+1 令p[i]=p[2M-i]
(即k回文子串l在L内)
若p[2M-i]>=R-i+1 令p[i]=R-i+1，再暴力向两边扩展
(即k回文子串l在L外)
——> 令p[i]=min(p[2M-i],R-i+1),并暴力向两边扩展
模板题
给出一个只由小写英文字符 a,b,c,…y,z 组成的字符串 S ,求 S 中最长回文串的长度
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N =1e5+10;
const ll mod = 1e9+7;
int manacher(string s)
{
int n=s.size();
vector<int> p(2*n+2);
vector<char> t(2*n+2);
int m=0;
t[++m]='$';
for(int i=0;i<n;i++)
{
t[++m]=s[i];
t[++m]='$';
}
int M=0,R=0;
for(int i=1;i<=m;i++)
{
if(i>R) p[i]=1;
else p[i]=min(p[2*M-i],R-i+1);
while(i-p[i]>=1 && i+p[i]<=m && t[i-p[i]]==t[i+p[i]]) p[i]++;
if(i+p[i]-1>R) M=i,R=i+p[i]-1;
}
return *max_element(p.begin(),p.end())-1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s;
cin>>s;
cout<<manacher(s)<<endl;
return 0;
}
|
