HDU 2087 剪花布条 KMP题解

KMP的应用，不过查找的时候注意一点就够了：查找到一个子串的时候，直接跳过整个串，而不是使用next数组前跳，因为根据题意需要剪出小饰条，小饰条之间不能重叠。

const int MAX_N = 1001;
char txt[MAX_N], pat[MAX_N];
int next[MAX_N], len;

void genNext()
{
	for (int i = 1, j = 0; i < len; )
	{
		if (pat[i] == pat[j]) next[i++] = ++j;
		else if (j > 0) j = next[j-1];
		else i++;
	}
}

int getSubs()
{
	int L = strlen(txt), ans = 0;
	for (int i = 0, j = 0; i < L; )
	{
		if (pat[j] == txt[i])
		{
			i++, j++;
			if (j == len)
			{
				ans++;
				j = 0;//can not overlap each substrings with:j=next[j-1];
			}
		}
		else if (j > 0) j = next[j-1];
		else i++;
	}
	return ans;
}

int main()
{
	while (scanf("%s %s", txt, pat) && txt[0] != '#')
	{
		len = strlen(pat);

		genNext();
		printf("%d\n", getSubs());
	}
	return 0;
}

HDU 2087 剪花布条 KMP题解,布布扣,bubuko.com

HDU 2087 剪花布条 KMP题解

原文：http://blog.csdn.net/kenden23/article/details/38517153