Cod sursa(job #1808225)

Utilizator Julian.FMI Caluian Iulian Julian. Data 17 noiembrie 2016 15:27:46
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <string.h>
#define pmax 2000099
using namespace std;
char p[pmax],s[pmax];
int sol[pmax],nr,urm[pmax];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{int k,m,n,i;
fin.getline(p,pmax);
m=strlen(p);
    urm[0]=-1;k=-1;
        for(i=1;i<m;i++)
        {   while(k>=0 && p[k+1]!=p[i])k=urm[k];
            if(p[k+1]==p[i])k++;
            urm[i]=k;
        }
    k=-1;
    fin.getline(s,pmax);
    n=strlen(s);
        for(i=0;i<n;i++)
        {   while(k>=0 && p[k+1]!=s[i])k=urm[k];
            if(p[k+1]==s[i])k++;
            if(k==m-1)
            {if(nr<1000)sol[++nr]=i-m+1;
                else nr++;
             k=urm[k];
            }

        }
        fout<<nr<<'\n';
        for(i=1;i<=min(nr,1000);i++)fout<<sol[i]<<'\n';

}