hdu 1711 Number Sequence

本题是KMP算法的典型运用，顺带说一下，csdn什么时候开始支持富文本格式的粘贴了？哈哈，现在不用点那个黄色的小笔去插入彩色代码了！

/* THE PROGRAM IS MADE BY PYY */

/*----------------------------------------------------------------------------//

Copyright (c) 2011 panyanyany All rights reserved.

URL : http://acm.hdu.edu.cn/showproblem.php?pid=1711

Name : 1711 Number Sequence

Date : Tuesday, May 3, 2011

Time Stage : 1 hours around

Result:

3905935

2011-05-03 23:30:20

Accepted

1711

1890MS

4268K

1631 B

C++

pyy

Test Data:

Review:

//----------------------------------------------------------------------------*/

#include <iostream>

#include <stdio.h>

using namespace std;

const int ms = 10010, ns = 1000010;

int tcase, n, m;

int major[ns], model[ms], next[ms];

void getNext( const int * arr )

{

int i, j, k;

next[1] = 0;

j = 1; i = 2;

while( i <= m )

{

if( arr[j] == arr[i] )

{

next[i] = next[j];

++j;

}

else

{

next[i] = j;

}

++i;

}

}

void kmp()

{

int i, j, k, start = -1, end = -1;

getNext( model );

j = 1; i = 1;

while( i <= n && j <= m )

{

if( major[i] == model[j] || j == 0 )

{

++i;

++j;

}

else

{

j = next[j];

}

}

if( j - 1 != m )

puts("-1");

else

printf("%d/n", i - j + 1);

}

int main()

{

int i, j, k;

while( cin >> tcase )

{

while( tcase-- )

{

cin >> n >> m;

for( i = 1; i <= n; ++i )

cin >> major[i];

for( i = 1; i <= m; ++i )

cin >> model[i];

kmp();

}

}

return 0;

}