HDU 2087 플 라 워 테이프 (첫 번 째 KMP 문제)

3515 단어 HDU
제목: http://acm.hdu.edu.cn/showproblem.php?pid=2087
 
#include <iostream>
#include <string>
using namespace std;

#define L1 1001
#define L2 1001


char s[L1], p[L2];
int nxt[L2], l1, l2;
int res;

void GetNext()
{
int k = -1, j = 0;
nxt[0] = -1;
while (j < l2)
{
if (k == -1 || p[j] == p[k])
{
j++, k++;
if (p[j] != p[k])
{
nxt[j] = k;
}
else
{
nxt[j] = nxt[k];
}
}
else
{
k = nxt[k];
}
}
}


int Kmp(int pos)
{
int i = pos, j = 0;
while (i < l1 && j < l2)
{
if (j == -1 || s[i] == p[j])
{
i++, j++;
}
else
{
j = nxt[j];
}
if (j == l2)
{
res++;
j = 0;
}
}
return res;

}


int main()
{

while (scanf("%s", s), s[0] != '#')
{
scanf("%s", p);
l1 = strlen(s);
l2 = strlen(p);
GetNext();
res = 0;
printf("%d
", Kmp(0));

}


return 0;
}

좋은 웹페이지 즐겨찾기