字符串入门
定义
前缀
对于字符串 \(S\)，从串首开始到某个位置 \(i\) 结束的子串，叫做 \(S\) 的一个前缀，除 \(S\) 本身外的所有前缀叫做 \(S\) 的真前缀。 #### 后缀
与前缀类似，从某位置 \(i\)
到串尾的一个字串叫做后缀，同样有真后缀。 ### 字典树/Trie
结构为一棵树，从根节点到树上某一结点的一条路径就是一个字符串。
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
43int id(char c){
if(c>='A'&&c<='Z')
return c-'A';
else if(c>='a'&&c<='z')
return c-'a'+26;
else
return c-'0'+52;
}
struct Trie{
int nxt[N][65],tot,cnt[N];
bool end[N];
void init(){
for(int i=0;i<=tot;i++)
for(int j=0;j<=64;j++)
nxt[i][j]=0;
for(int i=0;i<=tot;i++)
cnt[i]=0,end[i]=0;
tot=0;
return;
}
void insert(char s[]){
int p=0,len=strlen(s);
for(int i=0;i<len;i++){
int c=id(s[i]);
if(!nxt[p][c])
nxt[p][c]=++tot;
p=nxt[p][c];
cnt[p]++;
}
end[p]=1;
return;
}
int find(char s[]){
int p=0,len=strlen(s);
for(int i=0;i<len;i++){
int c=id(s[i]);
if(!nxt[p][c])
return 0;
p=nxt[p][c];
}
return cnt[p];
}
};1
2
3
4
5
6
7
8
9int j=0;
nxt[1]=0;//nxt[i]表示字串S[1...i]的最大border的长度
for(int i=2;i<=len;i++){
while(j&&s[j+1]!=s[i])
j=nxt[j];
if(s[j+1]==s[i])
j++;
nxt[i]=j;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19int j=0;
for(int i=2;i<=len2;i++){
while(j&&s2[j+1]!=s2[i])
j=nxt[j];
if(s2[j+1]==s2[i])
j++;
nxt[i]=j;
}
j=0;
for(int i=1;i<=len1;i++){
while(j&&s2[j+1]!=s1[i])
j=nxt[j];
if(s2[j+1]==s1[i])
j++;
if(j==len2){
printf("%d\n",i-j+1);
j=nxt[j];
}
}#。