串的KMP算法匹配实现

KMP中next[]的求解

void getNext(String t, int next[])
{
	int i = 1, j = 0;
	next[1] = 0;
	while (i < t.size)
	{
		if (j == 0 || t.ch[i] == t.ch[j])
		{
			i++;
			j++;
			next[i] = j; 
		}
		else
		{
			j = next[j];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

对KMP中next[]的优化nextval[]

void getnextval(String t, int next[], int nextval[])
{
	nextval[1] = 0;
	for (int j = 2; j <= t.size; j++)
	{
		if (t.ch[next[j]] == t.ch[j])
		{
			nextval[j] = nextval[next[j]];
		}
		else
		{
			nextval[j] = next[j];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

KMP算法实现

int index_KMP(String s, String t, int nextval[])
{
	int i = 1, j = 1;
	while (i <= s.size && j <= t.size)
	{
		if (j == 0 || s.ch[i] == t.ch[j])
		{
			i++;
			j++;
		}
		else
		{
			j = nextval[j];
		}
	}
	if (j > t.size)
	{
		//最后一个字符匹配成功i已经++
		return i - t.size;
	}
	else
	{
		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