KMP原理 点击
FZU 2275 Game
乍一看是个博弈的题目,实际上是重现里面比较简单的字符匹配。
只要B是0,那么A一定赢。只要A的长度小于B,那么B一定赢。
只有当A中可以搜索到B,也就是B或者B的反转是A的子串,那么A就可以赢。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5;
char a[N];
char b[N];
int next[N];
int n,m;
void getnext()
{
memset(next, 0, sizeof(next));
int n = strlen(b);
int i = 0, j = -1;
next[0] = -1;
while(i < n)
{
if(j == -1 || b[i] == b[j])
{
i++, j++;
if(b[i] == b[j])
next[i] = next[j];
else
next[i] = j;
}
else
j = next[j];
}
}
int kmp()
{
int n = strlen(a);
int m = strlen(b);
int i = 0, j = 0;
while(i < n && j < m)
{
if(j == -1 || a[i] == b[j])
{
i++, j++;
}
else
j = next[j];
}
if(j == m)
return i-m;
return -1;
}
int t;
int main()
{
cin>>t;
while(t--)
{
cin>>a>>b;
n =strlen(a);
m = strlen(b);
if(m == 1 && b[0] == '0')
{
printf("Alice\n");
continue;
}
if(n < m)
{
printf("Bob\n");
continue;
}
getnext();
int res = kmp();
if(res >= 0)
{
printf("Alice\n");
continue;
}
reverse(b, b + m);
getnext();
res = kmp();
if(res >= 0)
{
printf("Alice\n");
continue;
}
printf("Bob\n");
continue;
}
return 0;
}
上述是一个裸的KMP,POJ的这个是一个KMP的变形,就是改造判断条件。
题目要求是让 子串的各个序号的排名跟匹配串的排名一样,那么就算匹配成功,也就是说,对于每一个子串中的序号的数,
他前面的小于他的数的个数还有等于他的数的个数都要对应相等,把这个条件更换到KMP的条件就可以匹配了。
当时没做出来,参考了上海大学的模板,看懂后自己敲了一遍,雷同是有的。(KMP还有许多题,还有待练习
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
vector<int> ans;
int n, m, s;
int a[N], b[N];
int as[N][30], bs[N][30];
int next[N];
void init()
{
memset(as, 0, sizeof(as));
memset(bs, 0, sizeof(bs));
as[1][a[1]] = 1;
bs[1][b[1]] = 1;
for(int i = 2; i <= n; i++)
{
memcpy(as[i], as[i-1], sizeof(as[i-1]));
as[i][a[i]]++;
}
for(int i = 2; i <= m; i++)
{
memcpy(bs[i], bs[i-1], sizeof(bs[i-1]));
bs[i][b[i]]++;
}
}
void getnext()
{
int i = 1;
int j = 0;
int si,sj,ei,ej;
next[1] = 0;
while(i <= n)
{
si = sj = ei = ej = 0;
for(int k = 1; k < b[i]; k++)
{
si += bs[i][k] - bs[i-j][k];
}
ei = bs[i][b[i]] - bs[i-j][b[i]];
for(int k = 1; k < b[j]; k++)
{
sj += bs[j][k];
}
ej = bs[j][b[j]];
if(j == 0 || (si == sj && ei == ej))
{
i++, j++;
next[i] = j;
}
else
j = next[j];
}
}
void kmp()
{
int i = 1, j = 1;
int si, sj, ei, ej;
while(i <= n)
{
si = sj = ei = ej = 0;
for(int k = 1; k < a[i]; k++)
{
si += as[i][k] - as[i-j][k];
}
ei = as[i][a[i]] - as[i-j][a[i]];
for(int k = 1; k < b[j]; k++)
{
sj += bs[j][k];
}
ej = bs[j][b[j]];
if(j == 0 || (si == sj && ei == ej))
{
i++, j++;
}
else
j = next[j];
if(j == m+1)
{
ans.push_back(i - m);
j = next[j];
}
}
}
int main()
{
while(scanf("%d%d%d", &n, &m, &s) != EOF)
{
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= m; i++)
scanf("%d", &b[i]);
init();
ans.clear();
getnext();
kmp();
printf("%d\n", ans.size());
for(int i = 0; i < ans.size(); i++)
printf("%d\n", ans[i]);
}
return 0;
}