主串为s，模式串为p
s=abcdefg
p=efg

i
abcdefg

j
efg

首先从头开始比较，第一个字符不一样，那么新的下标m=i+ p.length,即s[m]=‘d’

然后在p中从后往前找’d’ ，即if(p[k]==s[m])

发现没有则将p后移到e，即s[i]=‘e’,p[j]=‘e’

若有则移动p使得下标k与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
int sunday(string s,string p )
{
	int i, j, k, m;
	int ls = s.size();
	int lp = p.size();
	i = j = 0;
	int num = 0;
	while (i <= ls - lp)
	{
		j = 0;
		if (s[i] == p[j])
		{
			int I = i, J = j;
			num++;
			while(J<lp)
			{
				if (s[I] != p[J])
				{
					num--;
					break;
				}
				I++;
				J++;
			}
			i++;
		}
		else
		{
			m = i + lp;
			for (k = lp-1; k>=0; k--)
			{
				if (p[k] == s[m])
				{
					i = m - k;
					break;
				}
			}
			if (k <0)
			{
				i = m + 1;
			}
		}
	}
	return num;
}

PS. 复杂度不低