Cod sursa(job #2392474)

Utilizator TeoDiDiaconescu Teodora TeoDi Data 30 martie 2019 08:30:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
#define N 2000005

int m,n;
char A[N],B[N];
int pi[N],pos[1024];

std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
/* void BNDM(char *x, int m, char *y, int n) {
  int B[N];
  int i, j, s, d, last;
  memset(B,0,N*sizeof(int));
  s=1;
  for (i=m-1; i>=0; i--){
    B[x[i]] |= s;
    s <<= 1;
  }
  j=0;
  while (j <= n-m){
    i=m-1; last=m;
    d = ~0;
    while (i>=0 && d!=0) {
      d &= B[y[j+i]];
      i--;
      if (d != 0){
    if (i >= 0)
      last = i+1;
    else
      {v[ct++]=j;}
       }
       d <<= 1;
     }
     j += last;
   }
  }
*/
void KMP()
{
	int q=0;
	pi[1]=0;
	for(int i=2;i<=m;++i)
	{
		while(q&&A[q+1]!=A[i]) q=pi[q];
		if(A[q+1]==A[i]) ++q;
		pi[i]=q;
	}
}

int main()
{
	int q=0,p=0;
	fin.getline(A,N);
	fin.getline(B,N);
	while((A[m]>='A' && A[m]<='Z') || (A[m]>='a' && A[m]<='z') || (A[m]>='0' && A[m]<='9')) ++m;
	while((B[n]>='A' && B[n]<='Z') || (B[n]>='a' && B[n]<='z') || (B[n]>='0' && B[n]<='9')) ++n;
	for (int i=m;i;--i) A[i]=A[i-1]; A[0] = ' ';
	for (int i = n; i; --i) B[i] = B[i-1]; B[0] = ' ';
	KMP();
	for (int i=1;i<=n;++i)
	{
		while(q&&A[q+1]!=B[i]) q=pi[q];
		if (A[q+1]==B[i]) ++q;
		if(q==m)
		{
			q=pi[m];
			++p;
			if (p<=1000)
				pos[p]=i-m;
		}
	}
	fout<<p<<'\n';
	for (int i=1;i<=std::min(p,1000);++i)
		fout<<pos[i]<<' ';
	return 0;
}