Cod sursa(job #2065869)

Utilizator GeorgeCalinPetruta George-Calin GeorgeCalin Data 14 noiembrie 2017 13:43:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <cstring>
#define nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int poz[1002];
int t[nmax];
char s[nmax];
char z[nmax];
int c=0,n,m;

void constr_vect_temp()
{
    int j=0;
    for(int i=2;z[i]!=NULL;i++)
    {
        while(z[j+1]!=z[i]&&j)
            j=t[j];
        if(z[j+1]==z[i])
            j++;
        t[i]=j;
    }
}

void cauta()
{
    int j=0;
    int m=strlen(z);
    for(int i=1;s[i]!=NULL;i++)
    {
        while(z[j+1]!=s[i]&&j)
            j=t[j];
        if(z[j+1]==s[i])
            j++;
        if(j==m-1)
        {
            j=t[j];
            c++;
            if(c<=1000)
                poz[c]=i-m+1;
        }
    }
}

int main()
{
    fin.getline(z,nmax);
    fin.getline(s,nmax);
    int n=strlen(s);
    int m=strlen(z);
    for(int i=n;i>=1;i--)
        s[i]=s[i-1];
    for(int j=m;j>=1;j--)
        z[j]=z[j-1];
    s[0]=' ';
    z[0]=' ';
    s[n+1]=NULL;
    z[m+1]=NULL;
    constr_vect_temp();
    cauta();
    fout<<c<<"\n";
    for(int i=1;i<=min(c,1000);i++)
    {
        fout<<poz[i]<<" ";
    }
    return 0;
}