- 科技
- 第三章使用数据结构 3.3.2字符串 kmp （大白书）
3.3 字符串
3.3.2Kmp
拓展kmp
模板
void getnxt(char *p
){
int m
= strlen(p
);
int i
=0, j
=-1;
nxt
[0]=-1;
while(i
<m
){
if(j
==-1||p
[i
]==p
[j
])nxt
[++i
]=++j
;
else j
=nxt
[j
];
}
}
bool kmp(char *p
, char *s
){
int n
=strlen(s
),m
=strlen(p
);
int i
=0,j
=0;
while(i
<n
){
if(j
==-1||s
[i
]==p
[j
])i
++,j
++;
else j
=nxt
[j
];
if(j
==m
)return true;
}
return false;
}
模板题
Number Sequence HDU - 1711
Oulipo HDU - 1686
剪花布条 HDU - 2087
贪心。
Blue Jeans POJ - 3080
暴力
Simpsons’ Hidden Talents HDU - 2594
kmp的应用
Clairewd’s message HDU - 4300
思维
Theme Section HDU - 4763
KMP
next应用循环节。
Period UVA - 1328
书本中eg
Period HDU - 1358
这题和上一题，基本一模一样。
Cyclic Nacklace HDU - 3746
Power Strings POJ - 2406
Processed:
0.009, SQL:
8
