Cod sursa(job #2231717)

Utilizator gavrisraulRaul Gavris gavrisraul Data 15 august 2018 18:22:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

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

const int maxn=2000005;
int n,m,i,j,nr,v[maxn],afis[1002];
char a[maxn],b[maxn];

int main(){
	fin.getline(a,maxn);
  fin.getline(b,maxn);
  n=strlen(a);
  m=strlen(b);
	for(i=1;i<n;i++){
  	while(a[j]!=a[i]&&j>0)
    	j=v[j-1];
    if(a[j]==a[i]){
    	v[i]=j+1;
      j++;
   	}
 	}
	j=0;
  for(i=0;i<m;i++){
  	while(b[i]!=a[j]&&j>0)
    	j=v[j-1];
    if(b[i]==a[j]){
    	if(j==n-1){
      	if(nr<=999)
        	afis[++nr]=i-n+1;
        else
        	nr++;
      }
  	j++;
    }
  }
  fout<<nr<<'\n';
  nr=min(nr,1000);
  for(i=1;i<=nr;i++)
  	fout<<afis[i]<<' ';
  return 0;
}