算法题整理——KMP

发表于 | 分类于 |

在做字符串的匹配时，我们有字符串S和T，现在想要从S中找到等于T的连续子串，一个朴素的想法是从S的每个字符开始，逐个和T的字符匹配，如果匹配不成功，再从S的下一个字符开始逐个匹配，这样的算法复杂度是O(NM)。

为了优化算法，我们注意到一个事实，即当我们匹配失败时，前面一定有一部分字符是匹配成功了的。我们寄希望于前面已经匹配成功的字符可以为我们带来信息，使我们尽量减少重复适配的次数。

例如T为abdcabc时，我们注意到如果匹配最后一位，即第二个c时，失败，那么我们至少知道前面的字符应该是abdcabx，x是和c匹配失败的字符，按朴素的算法思路，我们倒退回第一个a，然后前进到b，再开始新一轮的匹配，然后失败，前进到c……但仔细观察可以发现，倒退到b，d，c都是无意义的，我们必须倒退到某个地方，使得它是T的某个前缀才行，即倒退到第二个a，然后再将x与d比较。

这样，我们就有了KMP算法，KMP算法的精髓是next数组，其含义是如果S的当前位置i和T的位置j匹配失败了，那么我们直接把j退回到nextj，而非重新匹配。

求next数组的方法也很有意思，我们让T自身和自身匹配，如果匹配成功，后移，如果失败，那么其中一个退回到当前位置的next位置上继续匹配。

POJ1961_Period

描述

如果一个字符串S是由字符串T循环若干次组成的，那么T称为S的一个循环元，如果S没有比T更短的循环元，那么称T为S的最小循环元。

现在给出一个字符串S，对于S的每个前缀，若存在循环次数大于1的最小循环元，则输出最小循环元的长度及其循环次数。

解题思路

让字符串自匹配得next数组，此时字符串某个位置的前缀长度和相应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
47
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e6 + 5;

char input[N];
int nxt[N];
int unit[N];
int n, con = 0;

int main(){
	
	scanf("%d", &n); 
	while(n){
		scanf("%s", input + 1);
		
		printf("Test case #%d\n", ++con);
		
		nxt[1] = 0;
		for(int i = 2, j = 0; i <= n; ++i){
			while(j > 0 && input[j + 1] != input[i]) j = nxt[j];
			if(input[j + 1] == input[i]) ++j;
			nxt[i] = j;
		}
		
		//for(int i = 1; i <= n; ++i) printf("%d\n", nxt[i]);
		
		unit[1] = 1;
		for(int i = 2; i <= n; ++i){
			if(nxt[i] * 2 < i) unit[i] = i;
			else{
				if(i % unit[nxt[i]] == 0){
					unit[i] = unit[nxt[i]];
					printf("%d %d\n", i, i / unit[i]);
				}else unit[i] = i;
			}
		}
		
		//for(int i = 1; i <= n; ++i) printf("%d\n", unit[i]);
		printf("\n");
		scanf("%d", &n);
	}
	
	return 0;
}