HDU 4749 Parade Show 相对匹配的KMP

题目来源：HDU 4749 Parade Show

题意：从长度为n的序列最多能找到多少个不重叠的的连续的子串 和长度位m的序列的相对大小相同 

思路：转化成KMP 把原来的字母相同换成一个检测是否相对大小相同的函数 具体参考了http://blog.csdn.net/no__stop/article/details/11949743

#include <cstdio>
#include <cstring>
const int maxn = 100010;
int a[maxn], b[maxn], f[maxn];
int sum1[30][maxn], sum2[30][maxn];
int n, m, l;
bool ok1(int x, int y)
{
int s1 = 0, s2 = 0;
if(sum2[b[x]][x-1] != sum2[b[y]][y-1] - sum2[b[y]][y-x])
return false;
for(int i = 0; i < b[x]; i++)
s1 += sum2[i][x-1];
for(int i = 0; i < b[y]; i++)
{
s2 += sum2[i][y-1];
s2 -= sum2[i][y-x];
}
if(s1 != s2)
return false;
return true;
}
bool ok2(int x, int y)
{
int s1 = 0, s2 = 0;
if(sum2[b[x]][x-1] != sum1[a[y]][y-1] - sum1[a[y]][y-x])
return false;
for(int i = 0; i < b[x]; i++)
s1 += sum2[i][x-1];
for(int i = 0; i < a[y]; i++)
{
s2 += sum1[i][y-1];
s2 -= sum1[i][y-x];
}
if(s1 != s2)
return false;
return true;
}
void getFail()
{
f[0] = f[1] = 0;
for(int i = 2; i <= m; i++)
{
int j = f[i-1];
while(j && !ok1(j+1, i))
j = f[j];
f[i] = j+1;
}
}
void find()
{
int cnt = 0;
int j = 0;
for(int i = 1; i <= n; i++)
{
while(j && !ok2(j+1, i))
j = f[j];
j++;
if(j == m)
{
cnt++;
j = 0;
} 
}
printf("%d\n", cnt);
}

int main()
{
while(scanf("%d %d %d", &n, &m, &l) != EOF)
{
memset(sum1, 0, sizeof(sum1));
memset(sum2, 0, sizeof(sum2));
for(int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
a[i] = x;
for(int j = 1; j <= l; j++)
sum1[j][i] = sum1[j][i-1];
sum1[x][i]++;
}
for(int i = 1; i <= m; i++)
{
int x;
scanf("%d", &x);
b[i] = x;

for(int j = 1; j <= l; j++)
sum2[j][i] = sum2[j][i-1];
sum2[x][i]++;
}
getFail();
find();
}
return 0;
}