Cod sursa(job #1577854)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 23 ianuarie 2016 22:03:17
Problema Potrivirea sirurilor Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>
#define nmax 2000003
#include <cstring>

using namespace std;

char N[nmax],M[nmax];
int n,m,prefix[nmax],poz[nmax],rez=0;

int main(){

  freopen("strmatch.in","r",stdin);
  freopen("strmatch.out","w",stdout);

  N[0]=M[0]=' ';
  scanf("%s",N+1);n = strlen(N);
  scanf("%s",M+1);m = strlen(M);

  int k=0,i;
  for(i = 2;i < n;++i){
    while(k!=0 && N[k+1]!=N[i])k = prefix[k];
    if(N[i]==N[k+1])k++;
    prefix[i]=k;
  }

  for(i = 1;i < m;++i){
    while(k != 0 && M[i]!=N[k+1])k = prefix[k];
    if(M[i] == N[k+1])k++;
    if(k == n-1){
      rez++;
      if(rez<=1000)poz[rez] = i-n+1;
    }
  }

  printf("%d\n",rez);
  if(rez>1000)rez = 1000;
  for(i = 1;i<=rez;++i)printf("%d ",poz[i]);
  printf("\n");


return 0;
}