1. HDU 1711 Number Sequence
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 10007 int a[],b[N],next[N];
int n,m; void getnext()
{
next[] = -;
int i = ,j = -;
while(i<m)
{
if(j == - || b[i] == b[j])
{
++i,++j;
if(b[i] != b[j])
next[i] = j;
else
next[i] = next[j];
}
else
j = next[j];
}
} int kmp()
{
int i = -,j = -;
while(i<n && j<m)
{
if(j == - || a[i] == b[j])
i++,j++;
else
j = next[j];
}
if(j == m)
return i-j+;
return ;
} int main()
{
int t,i,res;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=;i<n;i++)
scanf("%d",&a[i]);
for(i=;i<m;i++)
scanf("%d",&b[i]);
if(n<m)
{
printf("-1\n");
continue;
}
getnext();
res = kmp();
if(res)
printf("%d\n",res);
else
printf("-1\n");
}
return ;
}
代码2：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 10007 int a[],b[N],next[N];
int n,m; void getnext()
{
next[] = -;
int i = ,j = -;
while(i<m-)
{
if(j == - || b[i] == b[j])
next[++i] = ++j;
else
j = next[j];
}
} int kmp()
{
int i = -,j = -;
while(i<n && j<m)
{
if(j == - || a[i] == b[j])
i++,j++;
else
j = next[j];
}
if(j == m)
return i-j+;
return ;
} int main()
{
int t,i,res;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=;i<n;i++)
scanf("%d",&a[i]);
for(i=;i<m;i++)
scanf("%d",&b[i]);
if(n<m)
{
printf("-1\n");
continue;
}
getnext();
res = kmp();
if(res)
printf("%d\n",res);
else
printf("-1\n");
}
return ;
}
2.POJ 3461 Oulipo
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 10007 char a[],b[N];
int next[N];
int n,m,cnt; void getnext()
{
next[] = -;
int i = ,j = -;
while(i<m)
{
if(j == - || b[i] == b[j])
next[++i] = ++j;
else
j = next[j];
}
} void kmp()
{
int i = -,j = -;
while(i<n && j<m)
{
if(j == - || a[i] == b[j])
i++,j++;
else
j = next[j];
if(j == m)
{
cnt++;
j = next[j];
}
}
} int main()
{
int t,i;
scanf("%d",&t);
while(t--)
{
scanf("%s",b);
scanf("%s",a);
n = strlen(a);
m = strlen(b);
getnext();
cnt = ;
kmp();
printf("%d\n",cnt);
}
return ;
}