Cod sursa(job #920458)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 20 martie 2013 15:02:13
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <string.h>
#define N 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char s[N],big[N];
int p[N],k,sl,bigl,i,sol[N],nr,j;

int main()
{
    fin>>s;
    fin>>big;
    sl=strlen(s);
    bigl=strlen(big);
    p[0]=0; k=0;
    for (i=1;i<sl;i++)
    {
    	while (k>0&&s[i]!=s[k]) k=p[k];
    	if (s[i]==s[k]) k++;
    	p[i]=k;
    }
    k=0; j=0;
    for (i=0;i<bigl;i++)
    {
    	if (s[k]==big[i])
    	{
    		if (k==sl-1) {nr++; sol[++j]=i-k; k=p[k];}
    		else k++;
    	}
    	else k=p[k];
    }
    fout<<nr<<"\n";
    for (i=1;i<=nr&&i<=1000;i++) fout<<sol[i]<<" ";
}