Cod sursa(job #392273)

Utilizator vicenzo_cnuStan Alexandru Dan vicenzo_cnu Data 7 februarie 2010 05:44:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<fstream>
#include<iostream>
#include<string.h>
using namespace std;
#define Nmax 2000005
char A[Nmax],B[Nmax];
int pi[Nmax],pos[1024];
int N,M;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

void prefix()
{int q=0,i;
  for(i=2,pi[1]=0;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()
{in>>A>>B;
N=strlen(B);
M=strlen(A);
int i;
  for(i=M;i;i--) A[i]=A[i-1]; A[0]=' ';
  for(i=N;i;i--) B[i]=B[i-1]; B[0]=' ';
int q=0,n=0; 
prefix(); 
  for(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)
        {n++;
        q=pi[M];
        if(n<=1000)
          pos[n]=i-M;
          }
}
out<<n<<endl;
if(n>1000)
n=1000;
for(i=1;i<=n;i++)
out<<pos[i]<<" ";
in.close();
out.close();
return 0;}