3270900_ac_344ms_14780k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

#define N 100005
#define K 25005
#define S 28

int cow[N];
int pat[K];
int n_spot[K][S];
int n_csp[N][S];
int pipei[K];
int loca[N];
int n, k, s, num;

int main()
{
 int i, j, pi, pj;
 int t1, t2, t3, t4;


 scanf("%d%d%d",&n, &k, &s);
 for (i = 0; i < n; i++)
   scanf("%d",&cow[i]);
 for (i = 0; i < k; i++)
	 scanf("%d",&pat[i]);

 memset(n_spot[0], 0, s+2);
 memset(n_csp[0], 0, s+2);
 n_spot[0][pat[0]] = 1;
 n_csp[0][cow[0]] = 1;

 for (i = 1; i < k; i++)
  {
    for (j = 1; j <= s; j++)
      n_spot[i][j] = n_spot[i-1][j];
    n_spot[i][pat[i]]++;
  }
 for (i = 1; i < n; i++)
  {
    for (j = 1; j <= s; j++)
      n_csp[i][j] = n_csp[i-1][j];
    n_csp[i][cow[i]]++;
  }

 pipei[0] = -1;
 pi = 0; pj = -1;
 while (pi < k)
  {
    if (pj == -1)
     {
      pipei[++pi] = ++pj;
      continue;
     }

    t1 = t2 = 0;
    for (i = 1; i < pat[pj]; i++)
      t1 += n_spot[pj][i];
    for (i = 1; i < pat[pi]; i++)
      t2 += n_spot[pi][i] - n_spot[pi-pj-1][i];
    t3 = n_spot[pj][pat[pj]];
    t4 = n_spot[pi][pat[pi]] - n_spot[pi-pj-1][pat[pi]];
    if (t1 == t2 && t3 == t4)
      pipei[++pi] = ++pj;
    else pj = pipei[pj];
 }

 pi = 0; pj = 0; num = 0;
 while (pi <= n-k+pj)
  {
    while (pi < n && pj < k)
     {
       if (pj == -1)
        { pi++; pj++; continue; }

       t1 = t2 = 0;
       for (i = 1; i < pat[pj]; i++)
         t1 += n_spot[pj][i];
       t3 = n_spot[pj][pat[pj]];

       if (pi == pj)
       {
        for (i = 1; i < cow[pi]; i++)
          t2 += n_csp[pi][i];
        t4 = n_csp[pi][cow[pi]];
       }
       else
       {
        for (i = 1; i < cow[pi]; i++)
          t2 += n_csp[pi][i] - n_csp[pi-pj-1][i];
        t4 = n_csp[pi][cow[pi]] - n_csp[pi-pj-1][cow[pi]];
       }

       if (t1 == t2 && t3 == t4)
         { pi++; pj++; }
       else pj = pipei[pj];
     }
    if (pj >= k)
	{
		loca[num++] = pi - pj + 1;
    	pj = pipei[k];
	}
  
  }

 printf("%d\n",num);
 for (i = 0; i < num; i++)
   printf("%d\n",loca[i]);

 return 0;
}