POJ-3167 Cow Patterns

Posted on | Edited on | In | Views:

题意

一个农场主有 N 头牛，每个牛都以它身上的斑点数作为标志，以斑点数作为标准对牛进行 rank 排序，定义牛的序列的相同性为第 i 头牛及其之前的牛的比他 rank 小的数量和与他 rank 相同的数量，比如：
1 4 4 3 2 1 和 2 10 10 7 3 2 是一样的模式串
要求数有多少个符合要求的模式串，并输出每个符合要求的子串的起始位置。

题解

定义一个函数 $getval(ch,str,l,r)$，返回的值为 $ch$ 在 $str[l~r]$ 中的真实值，即将 $str[l~r]$ 中的值排序离散化后 $ch$ 的值。则题意即为：在a串中找出一段长为m的区间[l,r]，使对任意的1≤i≤m，getval(a[l+i-1],a,l,r)均等于getval(b[i],b,1,m)getval的值，其实是返回某个数(数跟字符其实是一样的)在某堆数中的排名。是什么决定了一个数x的排名？是小于x的数的个数，等于x的数的个数。如果这两个个数与另一个y的两个个数都相等，那么x跟y在各自字符串的各自区间内的getval值就相等了

Image-7800823

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>
#include <vector>
#include <cstring>
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forr(i, r, l) for (int i = r; i >= l; i--)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define for0(i, n) for (int i = 0; i < n; i++)
#define meminf(a) memset(a, inf, sizeof(a))n
#define mem_1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define inlld(lld) scanf("%lld",&lld)
typedef unsigned long long ull;
#define inlf(f) scanf("%lf",&f)
#define ind(d) scanf("%d",&d)
#define ins(s) scanf("%s",s)
#define inf 0x3f3f3f3f
typedef long long ll;
#define pi acos(-1.0)
#define mod (int)(1e9+7)
#define N (int)(1.1e5)
using namespace std;

int Next[N],sump[N][30],now[30],sums[N][30],n,k;
vector<int>ans;
bool check(int l,int r,int sump[][30],int sums[][30],int *p,int*s){
  int lep=0,les=0;
  for1(i,p[l]-1)lep+=sump[l][i];
  for1(i,s[r]-1)les+=sums[r][i]-sums[r-l][i];
  if(lep==les&&sump[l][p[l]]==sums[r][s[r]]-sums[r-l][s[r]])return 1;
  else return 0;
}
void kmp_pre(int *p, int p_len, int Next[]) { // Next[i] 为满足 p[i-z...i-1]=p[0...z-1] 的最大 z 值(就是 p的自身匹配)
  int i = 0, j = Next[0] = -1;
  while (i < p_len) {
    while (j != -1 && !check(j,i,sump,sump,p,p)) j = Next[j];
    Next[++i] = ++j;
  }
}
void KMP(int *p, int *s) {  // p 是模式串，s 是主串
  int  i = 0, j = 0, p_len = k, s_len =n;
  for1(i,p_len){
    memcpy(sump[i],sump[i-1],30*sizeof(int));
    sump[i][p[i-1]]++;
  }
  for1(i,s_len){
    memcpy(sums[i],sums[i-1],sizeof(sums[i]));
    sums[i][s[i-1]]++;
  }
  kmp_pre(p, p_len, Next);
  while (i < s_len) {
    while (-1 != j && !check(j,i,sump,sums,p,s)) j = Next[j];
    i++;j++;
    if (j >= p_len) {
      ans.push_back(i);
      j = Next[j];
    }
  }
}
int p[N],S[N];
int main() {
#ifndef ONLINE_JUDGE
  // freopen("/Users/perpeternal/Documents/Sketch/data/in.dat", "r", stdin);
  // freopen("/Users/perpeternal/Documents/Sketch/data/out.dat","w",stdout);
#endif
  //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int q;
  scanf("%d%d%d",&n,&k,&q);
  for0(i,n)ind(S[i]);
  for0(i,k)ind(p[i]);
  KMP(p,S);
  //puts("");
  printf("%d\n",(int)ans.size());
  for0(i,ans.size())printf("%d\n",ans[i]-k+1);
  return 0;
}