首页 > 代码库 > HDU 2087 剪花布条 KMP题解

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;
}