杭电 hdu 2087 剪花布条

第二次做这题，才发现，这一题的数据真是水得可以，连第一次本应错误的代码也能过……第一次在kmp() 函数里面，在if( len == j ) 之后 本应是 { ++cnt ; j = 0 ; } 才对。

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.

URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2087
Name  : 2087 剪花布条

Date  : Wednesday, August 17, 2011
Time Stage : half an hours around

Result:

Test Data:
4440850	2011-08-17 21:55:06	Accepted 2087 0MS 200K 1590 B C++ pyy


Review:
确实不太难，现在却理解不了以前的做法了，好奇怪……又变得懵懂了我……
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

#define infinity    0x7f7f7f7f
#define minus_inf    0x80808080

#define MAXSIZE 1009

char model[MAXSIZE], pattn[MAXSIZE] ;
int next[MAXSIZE], len_1, len_2 ;

void getNext (char *ps, char *pe)
{
	int i, j ;
	i = 0 ;
	j = -1 ;
	next[0] = -1 ;

	while (i < pe - ps)
	{
		if (j == -1 || ps[i] == ps[j])
		{
			++i ; ++j ;
			if (ps[i] != ps[j])
				next[i] = j ;
			else
				next[i] = next[j] ;
		}
		else
		{
			j = next[j] ;
		}
	}
}

int kmp (char *ms, char *me, char *ps, char *pe)
{
	int i, j, cnt ;
	i = j = cnt = 0 ;

	getNext (ps, pe) ;

	while (i < me - ms)
	{
		if (j == -1 || ms[i] == ps[j])
		{
			++i ; ++j ;
		}
		else
		{
			j = next[j] ;
		}
		if (j == pe - ps)
		{
			++cnt ;
			j = 0 ;
		}
	}

	return cnt ;
}

int main ()
{
	while (scanf ("%s", model), *model != '#')
	{
		scanf ("%s", pattn) ;
		getchar () ;
		printf ("%d\n", kmp (model, model +strlen (model), pattn, pattn + strlen (pattn))) ;
	}
	return 0 ;
}

--------------------------------------------第一次的分割线-------------------------------------------------------

不搜不知道，一搜吓一跳！原来这题：1.可以不用KMP算法做，2.可以调用库函数来做！

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
	Copyright (c) 2011 panyanyany All rights reserved.

	URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2087
	Name  : 2087 剪花布条

	Date  : Monday, May 6, 2011
	Time Stage : half an hours around

	Result:

Test Data:
3929798	2011-05-09 02:40:39	Accepted	2087
15MS	280K	1215 B
C++	pyy


Review:
貌似是一题比较简单的KMP
//----------------------------------------------------------------------------*/
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int size = 1010;
char str[size], piece[size];
int next[size];

void getNext()
{
	int i, j, k;
	const int len = (int)strlen(piece);
	i = 0;
	j = 1;
	next[0] = -1;
	while( j < len )
	{
		if( piece[i] == piece[j] )
		{
			next[j] = next[i];
			++i;
		}
		else 
		{
			next[j] = i;
		}
		++j;
	}
}

int kmp()
{
	int i, j;
	int cnt = 0;
	const int leng = strlen(str), len = strlen(piece);
	getNext();
	for( i = j = 0; i < leng; )
	{
		if( len == j )
			++cnt;
		if( str[i] == piece[j] || -1 == j )
		{
			++i;
			++j;
		}
		else 
		{
			j = next[j];
		}
	}
	if( leng == i && len == j )
		++cnt;
	return cnt;
}

int main()
{
	int i, j;
	while( cin >> str >> piece && strcmp(str, "#") )
	{
		cout << kmp() << endl;
	}
	return 0;
}