Cod sursa(job #2231489)

Utilizator gavrisraulRaul Gavris gavrisraul Data 14 august 2018 17:03:19
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int maxn=2000004;
char sirA[maxn],sirB[maxn];
int M,N,pi[maxn],pos[1026];

void prefix(){
  int i,q=0;
  for(i=2,pi[1]=0;i<=M;++i){
    while(q&&sirA[q+1]!=sirA[i])
      q=pi[q];
    if(sirA[q+1]==sirA[i])
      ++q;
      pi[i]=q;
  }
}
int main(){
  fin.getline(sirA,maxn);
  fin.getline(sirB,maxn);
  int q=0,n=0,i;
  for (; (sirA[M] >= 'A' && sirA[M] <= 'Z') || (sirA[M] >= 'a' && sirA[M] <= 'z') 

            || (sirA[M] >= '0' && sirA[M] <= '9'); ++M);

    for (; (sirB[N] >= 'A' && sirB[N] <= 'Z') || (sirB[N] >= 'a' && sirB[N] <= 'z')

            || (sirB[N] >= '0' && sirB[N] <= '9'); ++N);

    for (i = M; i; --i) sirA[i] = sirA[i-1]; sirA[0] = ' ';

    for (i = N; i; --i) sirB[i] = sirB[i-1]; sirB[0] = ' '; 


  prefix();
  for(i=1;i<=N;++i){
    while(q&&sirA[q+1]!=sirB[i])
      q=pi[q];
    if(sirA[q+1]==sirB[i])
      ++q;
    if(q==M){
      q=pi[M];
      ++n;
      if(n<=1000)
        pos[n]=i-M;
    }
  }
  fout<<n<<'\n';
  for(i=1;i<=min(n,1000);++i)
    fout<<pos[i]<<' ';
  return 0;
}